Submission #313358

#	Time	Username	Problem	Language	Result	Execution time	Memory
313358		KWang31	Torrent (COI16_torrent)	Java	0 / 100	2007 ms	107772 KiB

torrent

import java.io.*; import java.util.*;
public class torrent {

    /**
     * COI 16/4
     * DP on tree + Binary Search
     */
    static ArrayList<Integer> arl[];
    static int[] par;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int A=Integer.parseInt(st.nextToken())-1;
        int B=Integer.parseInt(st.nextToken())-1;
        arl=new ArrayList[N];
        for (int i = 0; i < N; i++) {
            arl[i]=new ArrayList<>();
        }
        int x,y;
        for (int i = 0; i < N-1; i++) {
            st=new StringTokenizer(br.readLine());
            x=Integer.parseInt(st.nextToken())-1;
            y=Integer.parseInt(st.nextToken())-1;
            arl[x].add(y); arl[y].add(x);
        }
        //Step 1: Find the path between A and B with parent pointer
        par=new int[N]; dp=new int[N];
        dp(-1,-1,A); par[A]=-1;
        dp(par[B],-1,B); 
        
        int BB=B; ArrayList<Integer> p=new ArrayList<>();//dp of nodes in the path
        while(par[BB]!=A){
            //System.out.println(BB);
            dp(BB,par[par[BB]],par[BB]);
            p.add(dp[par[BB]]);
            BB=par[BB];
        }
        
        int[] ac=new int[arl[A].size()-1]; int cnt=0;
        for (int i : arl[A]) {
            if(i!=BB){
                
                ac[cnt]=dp[i];
                
                cnt++;
            }
        }
        int[] bc=new int[arl[B].size()-1]; cnt=0;
        for (int i : arl[B]) {
            if(i!=par[B]){
                bc[cnt]=dp[i]; cnt++;
            }
        }
        Arrays.sort(ac); Arrays.sort(bc);
        int[] prefA=new int[Math.max(0,arl[A].size()-1)];
        if(arl[A].size()>=2){
            prefA[0]=ac[0]+1;
            for (int i = 1; i < arl[A].size()-1; i++) {
                prefA[i]=1+Math.max(prefA[i-1],ac[i]);
            }
        }
        int[] prefB=new int[Math.max(0,arl[B].size()-1)];
        if(arl[B].size()>=2){
            prefB[0]=bc[0]+1;
            for (int i = 1; i < arl[B].size()-1; i++) {
                prefB[i]=1+Math.max(prefB[i-1],bc[i]);
            }
        }
        /*
        System.out.println("dp :"+Arrays.toString(dp));
        System.out.println("ac :"+Arrays.toString(ac));
        System.out.println("bc :"+Arrays.toString(bc));
        System.out.println("prefA:"+Arrays.toString(prefA));
        System.out.println("prefB :"+Arrays.toString(prefB));
        System.out.println("p: "+p);
        */
        int l=1; int r=dp[A];
        while(l<r){
            int m=(l+r)/2;
            //We simulate what happens
            int ptDA=0; int CApter=arl[A].size()-2;
            int ptDB=p.size()-1; int CBpter=arl[B].size()-2;
            boolean ok=false;
            
            for (int mid=m; mid>0; mid--) {
                if(l==1 && r==3){
                    //System.out.println(mid);
                    //System.out.println(ptDA+" ptDA");
                    //System.out.println(ptDB+" ptDB");
                    //System.out.println(CApter+" CApter");
                    //System.out.println(CBpter+" CBpter");
                }
                if(CApter>=0){
                    if(prefA[CApter]>mid){
                        break;//ok=false
                    }else if(prefA[CApter]==mid){
                        CApter--;
                    }else if(ptDA<p.size() && p.get(ptDA)>=mid){
                        break;
                    }else{
                        ptDA++;
                    }
                }else if(ptDA<p.size() && p.get(ptDA)>=mid){
                     break;
                }else{
                     ptDA++;
                }
                if(CBpter>=0){
                    if(prefB[CBpter]>mid){
                        break;//ok=false
                    }else if(prefB[CBpter]==mid){
                        CBpter--;
                    }else if(ptDB>=0 && p.get(ptDB)>=mid){
                         break;
                    }else{
                         ptDB--;
                    }
                    
                }else if(ptDB>=0 && p.get(ptDB)>=mid){
                     break;
                }else{
                     ptDB--;
                }
                if(CApter==-1 && CBpter==-1 && ptDA>ptDB){
                    ok=true; break;
                }
            }
            if(!ok){
                l=m+1;
            }else{
                r=m;
            }
            //System.out.println(l+" "+r);
        }
        System.out.println(l);
    }
    public static void dp(int p, int p2, int v){
        int[] c;
        if(p>=0){
            if(p2>=0){
                c=new int[arl[v].size()-2];
            }else{
                c=new int[arl[v].size()-1];
            }
        }else{
            c=new int[arl[v].size()];
        }
        int k=0;
        for (int i : arl[v]) {
            if(i==p || i==p2)continue;
            dp(v,-1,i);
            par[i]=v;
            c[k]=dp[i]; k++;
        }
        Arrays.sort(c);
        if(k==0){
            dp[v]=0;
        }else{
            int max=c[k-1]+1;
            for (int i = 2; i <= k; i++) {
                max=Math.max(max,i+c[k-i]);
            }
            dp[v]=max;
        }
        
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69