이 코드는 알고리즘 해결전략 책에있는 C++코드를 자바코드로 바꿔서 나온 코드입니다.(RMQ 알고리즘이용)
책에 나온거 참고해서 한건데 자꾸 RTE(메모리초과)가 나오는데 어디서 잘못된걸까요????? 도와주시면 감사하겠습니다.
public class Main {
final static int MAX_N=100000;
private static int N;
private static int M;
private static int nextSerial;
private static int noToserial[]=new int[100000];
private static int serialTono[]=new int[100000];
private static int loclnTrip[]=new int[100000];
private static int depth[]=new int[100000];
static ArrayList<Integer> child[]=new ArrayList[100000];
public static void main(String[] args) {
// TODO Auto-generated method stub
try{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer=new BufferedWriter(new OutputStreamWriter(System.out));
int Cases=Integer.parseInt(reader.readLine());
while(Cases-->0){
for(int i=0;i<MAX_N;i++){
child[i]=new ArrayList<Integer>();
}
String input[]=reader.readLine().split(" ");
N=Integer.parseInt(input[0]);
M=Integer.parseInt(input[1]);
int parent;
input=reader.readLine().split(" ");
for(int i=1;i<N;i++){
parent=Integer.parseInt(input[i-1]);
child[parent].add(i);
}
RMQ rmq=prepareRMQ();
int a,b;
for(int i=0;i<M;i++){
input=reader.readLine().split(" ");
a=Integer.parseInt(input[0]);
b=Integer.parseInt(input[1]);
writer.append(String.valueOf(distance(rmq,a,b)));
writer.append("\n");
}
}
writer.flush();
writer.close();
reader.close();
}catch(Exception e){
e.printStackTrace();
}
}
private static int distance(RMQ rmq,int u, int v) {
// TODO Auto-generated method stub
int lu=loclnTrip[u];
int lv=loclnTrip[v];
if(lu>lv){
int temp=lu;
lu=lv;
lv=temp;
}
int lca=serialTono[rmq.query(lu,lv)];
return depth[u]+depth[v]-2*depth[lca];
}
private static RMQ prepareRMQ(){
nextSerial=0;
ArrayList<Integer> trip = new ArrayList<Integer>();
traverse(0,0,trip);
return new RMQ(trip);
}
private static void traverse(int here, int d, ArrayList<Integer> trip) {
// TODO Auto-generated method stub
noToserial[here]=nextSerial;
serialTono[nextSerial]=here;
++nextSerial;
depth[here]=d;
loclnTrip[here]=trip.size();
trip.add(noToserial[here]);
for(int i=0;i<child[here].size();i++){
traverse(child[here].get(i),d+1,trip);
trip.add(noToserial[here]);
}
}
}
class RMQ{
int n;
int []rangeSize;
RMQ(int []array){
n=array.length;
rangeSize=new int[n*4];
init(array,1,0,n-1);
}
RMQ(ArrayList<Integer> array){
n=array.size();
rangeSize=new int[n*4];
init(array,1,0,n-1);
}
private int init(ArrayList<Integer> array, int node, int left,int right) {
// TODO Auto-generated method stub
if(left==right)
return rangeSize[node]=array.get(left);
int mid=(left+right)/2;
int leftMin=init(array,node*2,left,mid);
int rightMin=init(array,node*2+1,mid+1,right);
return Math.min(leftMin,rightMin);
}
private int init(int[] array, int node, int left, int right) {
// TODO Auto-generated method stub
if(left==right)
return rangeSize[node]=array[left];
int mid=(left+right)/2;
int leftMin=init(array,node*2,left,mid);
int rightMin=init(array,node*2+1,mid+1,right);
return Math.min(leftMin,rightMin);
}
int query(int left,int right){
return query(left,right,1,0,n-1);
}
private int query(int left, int right, int node, int leftNode, int rightNode) {
// TODO Auto-generated method stub
if(right<leftNode || left>rightNode)
return 1000000;
if(leftNode>=left && rightNode<=right)
return rangeSize[node];
int mid=(leftNode+rightNode)/2;
return Math.min(query(left,right,node*2,leftNode,mid),
query(left,right,node*2+1,mid+1,rightNode));
}
clearpal6
이 코드는 알고리즘 해결전략 책에있는 C++코드를 자바코드로 바꿔서 나온 코드입니다.(RMQ 알고리즘이용)
책에 나온거 참고해서 한건데 자꾸 RTE(메모리초과)가 나오는데 어디서 잘못된걸까요????? 도와주시면 감사하겠습니다.
public class Main {
}
class RMQ{
int n;
}
9년 전