Submission #314025

#	Time	Username	Problem	Language	Result	Execution time	Memory
314025		KWang31	Torrent (COI16_torrent)	Java	100 / 100	1853 ms	149424 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
        p.add(B);
        int X=1;
        while(par[BB]!=A){
            //System.out.println(BB);
            dp(BB,par[par[BB]],par[BB]);
            X++;
            p.add(par[BB]);
            BB=par[BB];
        }
        p.add(A);
        int[][] pref=new int[X+1][0]; int cnt=0;
        //Add B first
        pref[0]=new int[arl[B].size()-1];
        for (int i : arl[B]) {
            
            if(i!=par[B]){
                pref[0][cnt]=dp[i]; cnt++;
            }
        }
        Arrays.sort(pref[0]);
        
        int cur,next;
        for (int i = 1; i < X; i++) {
            cur=p.get(i); next=p.get(i+1); cnt=0;
            
            pref[i]=new int[arl[cur].size()-2];
            for (int j : arl[cur]) {
                if(j!=next && j!=p.get(i-1)){
                    pref[i][cnt]=dp[j]; cnt++;
                }
            }
            Arrays.sort(pref[i]);
        }
        
        pref[X]=new int[arl[A].size()-1]; cnt=0;
        for (int i : arl[A]) {
            if(i!=BB){
                
                pref[X][cnt]=dp[i];
                
                cnt++;
            }
        }
        Arrays.sort(pref[X]);
        
        
        for (int i = 0; i <=X; i++) {
            if(pref[i].length>0){
                pref[i][0]++;
                for (int j = 1; j < pref[i].length; j++) {
                    pref[i][j]=1+Math.max(pref[i][j-1],pref[i][j]);
                }
            }
            
        }
        
        
        int l=0; int r=dp[A];
        
        while(l<r){
            int m=(l+r)/2;
            
            int ptDB=0; //Tracks which node B's pointer is on
            int ptCB=pref[ptDB].length-1; 
            int ptDA=p.size()-1; 
            int ptCA=pref[ptDA].length-1;
            boolean ok=false;
            
            for (int mid=m; mid>0; mid--) {
                if(m==2){
                    System.out.println(mid+" "+ptDB+" "+ptCB+" "+ptDA+" "+ptCA);
                }
                if(ptCB>=0 && pref[ptDB][ptCB]>mid){
                    break;
                }else if(ptCB>0 && pref[ptDB][ptCB]==mid){
                    ptCB--;
                }else{
                    ptDB++;ptCB=pref[ptDB].length-1; 
                }
                if(ptCA>=0 && pref[ptDA][ptCA]>mid){
                    break;
                }else if(ptCA>0 && pref[ptDA][ptCA]==mid){
                    ptCA--;
                }else{
                    ptDA--; ptCA=pref[ptDA].length-1;
                }
               
                if(ptDB>ptDA){
                    ok=true; break;
                }else if(ptDB==ptDA){
                    if(Math.min(ptCA,ptCB)==-1){
                        ok=true; break;
                    }else if(pref[ptDB][Math.min(ptCA,ptCB)]>mid-1){
                        break;
                    }else{
                        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: 31 / 31
• Subtask 2: 69 / 69