Submission #301404

#	Time	Username	Problem	Language	Result	Execution time	Memory
301404		KWang31	Connecting Supertrees (IOI20_supertrees)	Java	40 / 100	510 ms	57760 KiB

supertrees

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

    static class Pair implements Comparable<Pair>{
        int v; int l0;
        public Pair(int a, int b){
            this.v=a; this.l0=b;
        }
        public int compareTo(Pair other){//Sort by l0 values
            if(this.l0>other.l0)return 1;
            if(this.l0<other.l0)return -1;
            if(this.v<other.v)return -1;
            if(this.v>other.v)return 1;
            return 0;
        }
    }
    /*
    public static void main(String[] args) throws IOException {
        // Tester code
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        int[][] p=new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st=new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                p[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(construct(p));
    }
*/
public static int construct(int[][] p){
        int N=p.length;
        
        int[][] b=new int[N][N];
        int[] rank1=new int[N];//Consider the graph of 1-edges
        int[] rank0=new int[N];//Graph of 1,2-edges
        
        int[] par1=new int[N];
        int[] par0=new int[N];
        
        for (int i =0; i < N; i++) {
            par1[i]=i; par0[i]=i; 
        }
        int ii,jj;
        for (int i = 0; i < N; i++) {
            for (int j =0; j < N; j++) {
                if(i==j)continue;
                if(p[i][j]==1){
                    ii=find(i,par1); jj=find(j,par1);
                    if(ii!=jj){
                        if(rank1[ii]<rank1[jj]){
                            par1[ii]=jj;
                        }else if(rank1[ii]==rank1[jj]){
                            par1[ii]=jj; rank1[jj]++;
                        }else{
                            par1[jj]=ii;
                        }
                    }
                    ii=find(i,par0); jj=find(j,par0);
                    if(ii!=jj){
                        if(rank0[ii]<rank0[jj]){
                            par0[ii]=jj; 
                        }else if(rank0[ii]==rank0[jj]){
                            par0[ii]=jj; rank0[jj]++;
                        }else{
                            par0[jj]=ii;
                        }
                    }
                }else if(p[i][j]==2){
                    ii=find(i,par1); jj=find(j,par1);
                    if(ii==jj){//Deals with case i)
                        return 0;
                    }
                    
                    ii=find(i,par0); jj=find(j,par0);
                    if(ii!=jj){
                        if(rank0[ii]<rank0[jj]){
                            par0[ii]=jj;
                        }else if(rank0[ii]==rank0[jj]){
                            par0[ii]=jj; rank0[jj]++;
                        }else{
                            par0[jj]=ii;
                        }
                    }
                }else if(p[i][j]==3){
                    return 0;
                }else{
                    ii=find(i,par0); jj=find(j,par0);
                    if(ii==jj)return 0;
                }
            }
        }
        //Now for every 1-2 component, we need to find number of 1-leaders
        //That is the length of cycle. I lose if its length is 2 (length 1 is just a tree)
        boolean[] done=new boolean[N];
        int[] ans=new int[N];
        for (int i = 0; i < N; i++) {
            ans[i]++;//Include itself
        }
        for (int i = 0; i < N; i++) {
            ii=find(i,par1);
            if(!done[ii]){
                jj=find(ii,par0);
                if(ii!=jj){
                    ans[jj]++;
                }
                done[ii]=true;
            }
        }
         //System.out.println(Arrays.toString(ans));
        for (int i = 0; i < N; i++) {
            if(ans[i]==2){
                return 0;
            }
        }
        
        
        TreeSet<Pair> leads=new TreeSet<>();//Include leaders of all 1-components
        
        for (int i = 0; i < N; i++) {//1-graphs
            
            ii=find(i,par1);
            if(ii!=i){
                b[i][ii]=1; b[ii][i]=1;
                
                //Same component guys don't matter
            }
            if(find(ii,par0)!=ii){
                leads.add(new Pair(ii,find(ii,par0)));
            }
            
        }
        
        int prevl=-1;int prevv=0; 
        //Completes the cycle
        int save=0;
        for (Pair q: leads) {
            //System.out.println(q.v+" "+q.l0+" "+prevv);
            if(prevl!=q.l0){
                if(prevl!=-1){
                    //System.out.println(prevv);
                    b[prevv][prevl]=1;b[prevl][prevv]=1;
                } 
                b[q.v][q.l0]=1; b[q.l0][q.v]=1;
                prevl=q.l0; 
                
            }else{
                b[q.v][prevv]=1; b[prevv][q.v]=1;
                
            }
            prevv=q.v; save=q.l0;
        }
        if(prevv!=save){b[prevv][save]=1; b[save][prevv]=1;}
        //Last fill
        //The leaders of every component forms a cycle as long as they're connected in the >=1 graph
        grader.build(b);
        /*
        for (int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(b[i]));
        }
        */
        return 1;
    }
    
    public static int find(int x, int[] par){
        if(par[x]==x)return x;
        int ans=find(par[x],par);
        par[x]=ans; return ans;
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4