FAMILYTREE 계속해서 메모리 초과가 뜨네요...

  • clearpal6
    clearpal6

    이 코드는 알고리즘 해결전략 책에있는 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));
    }

    }


    9년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    자바 메모리 사용량이 많아서 그런 것 같습니다. 해당 문제 메모리 제한을 256mb로 늘렸으니 다시 시도해 보세요. 재채점해보니 정상적으로 채점되네요.


    9년 전 link
  • clearpal6
    clearpal6

    감사합니다^^


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.