제출 #951107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951107		imabhideep	Railway (BOI17_railway)	Java	0 / 100	1050 ms	320508 KiB

railway

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.sql.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class railway {
    static int n;
    static ArrayList<Integer> tree[];
    static ArrayList<ArrayList<Integer>> pathBinaryLifting[][];
    static HashMap<ArrayList<Integer>,Integer> userPathIndex;
    static Tree t;
    static int k;
    public static void main(String[] args)throws IOException {
        BufferedReader x=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        StringTokenizer st=new StringTokenizer(x.readLine());
        userPathIndex=new HashMap<>();
        n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        k=Integer.parseInt(st.nextToken());
        pathBinaryLifting=new ArrayList[n+1][20];
        tree=new ArrayList[n+1];
        for(int i=0;i<=n;i++)tree[i]=new ArrayList<>();
        for(int i=0;i<n-1;i++){
            st=new StringTokenizer(x.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            userPathIndex.put(getPathStructure(a,b),i);
            tree[a].add(b);
            tree[b].add(a);
        }
        t=new Tree();
//        t.printPathBinaryLifting();
        HashMap<ArrayList<Integer>, Integer> hm=new HashMap<>();
        for(int i=0;i<m;i++){
            st=new StringTokenizer(x.readLine());
            int noOfStations=Integer.parseInt(st.nextToken());
            int stationA=Integer.parseInt(st.nextToken());
            for(int j=0;j<noOfStations-1;j++){
                int stationB=Integer.parseInt(st.nextToken());
                insertPaths(hm,stationA, stationB);
                stationA=stationB;
            }
        }
        ArrayList<Integer> answer=new ArrayList<>();
        for(Map.Entry<ArrayList<Integer>, Integer> mp:hm.entrySet()){
            ArrayList<Integer> arr=mp.getKey();
            int times=mp.getValue();
            if(times>=k){
                answer.add(userPathIndex.get(arr)+1);
            }
        }
        pw.println(answer.size());
        for(int i:answer)pw.print(i+" ");
        pw.println();
        pw.close();
    }
    static void insertPaths(HashMap<ArrayList<Integer>,Integer> hm, int stationA, int stationB){
        ArrayList<ArrayList<Integer>> paths=t.getPaths(stationA,stationB);
        for(ArrayList<Integer> i:paths){
            hm.put(i,hm.getOrDefault(i,0)+1);
        }
//        System.out.println(stationA+"->"+stationB+": "+paths);
    }
    static ArrayList<ArrayList<Integer>> getPaths(int a, int b){
        int lca=t.LCA(a,b);
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();

        int height=t.depth[a]-t.depth[lca];
        int level=0;
        while(height>0){
            if((height&1)==1){
                list.addAll(pathBinaryLifting[a][level]);
                a=t.binaryLifting[a][level];
            }
            level+=1;
            height=height>>1;
        }
        height=t.depth[b]-t.depth[lca];
        level=0;
        while(height>0){
            if((height&1)==1){
                list.addAll(pathBinaryLifting[b][level]);
                b=t.binaryLifting[a][level];
            }
            level+=1;
            height=height>>1;
        }
        return list;
    }
    static ArrayList<Integer> getPathStructure(int a, int b){
        ArrayList<Integer> path=new ArrayList<>();
        if(a>b){
            int temp=a;
            a=b;
            b=temp;
        }
        path.add(a);
        path.add(b);
        return path;
    }
    static class Tree extends railway {
        static int HEIGHT=20;
        static int depth[];
        static int binaryLifting[][];
        Tree(){
            binaryLifting=new int[n+1][20];
            depth=new int[n+1];
            dfs(1,0);
        }
        static int LCA(int a, int b) {
            if(depth[a]>depth[b]){
                int temp=a;
                a=b;
                b=temp;
            }
            // depth of a is less than depth of b
            b=jump(b,depth[b]-depth[a]);
            if(a==b){
                return a;
            }
            for(int i=HEIGHT-1;i>=0;i--){
                if(binaryLifting[a][i]!=binaryLifting[b][i]){
                    a=binaryLifting[a][i];
                    b=binaryLifting[b][i];
                }
            }
            return binaryLifting[a][0];
        }
        static int jump(int a, int height){
            int level=0;
            while(height!=0){
                if((height&1)==1){
                    a=binaryLifting[a][level];
                }
                level+=1;
                height=height>>1;
            }
            return a;
        }
        static void printBinaryLifting(){
            for(int i=0;i<=n;i++){
                System.out.print(i+" : ");
                for(int j=0;j<HEIGHT;j++){
                    System.out.print(binaryLifting[i][j]+" ");
                }
                System.out.println();
            }
        }
        static void printPathBinaryLifting(){
            for(int i=0;i<=n;i++){
                System.out.print(i+" : ");
                for(int j=0;j<HEIGHT;j++){
                    System.out.print(pathBinaryLifting[i][j]+" | ");
                }
                System.out.println();
            }
        }
        static void dfs(int node, int par){
            binaryLifting[node][0]=par;
            depth[node]=depth[par]+1;
            pathBinaryLifting[node][0]=new ArrayList<>();
            if(par!=0) {
                pathBinaryLifting[node][0].add(getPathStructure(par, node));
            }
            for(int level=1;level<HEIGHT;level++){
                binaryLifting[node][level]=binaryLifting[binaryLifting[node][level-1]][level-1];
                pathBinaryLifting[node][level]=new ArrayList<>();
                pathBinaryLifting[node][level].addAll(pathBinaryLifting[node][level-1]);
                if(pathBinaryLifting[binaryLifting[node][level-1]][level-1]==null){
                    pathBinaryLifting[binaryLifting[node][level-1]][level-1]=new ArrayList<>();
                }
                pathBinaryLifting[node][level].addAll(pathBinaryLifting[binaryLifting[node][level-1]][level-1]);
            }
            for(int childNode:tree[node]){
                if(childNode==par)continue;
                dfs(childNode, node);
            }
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Note: railway.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25