Submission #301375

#	Time	Username	Problem	Language	Result	Execution time	Memory
301375		KWang31	Connecting Supertrees (IOI20_supertrees)	Java	21 / 100	473 ms	58316 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[] siz0=new int[N];//Component size: size of 3 may arouse exceptions
        int[] par1=new int[N];
        int[] par0=new int[N];
        
        for (int i =0; i < N; i++) {
            par1[i]=i; par0[i]=i; siz0[i]=1;
        }
        int ii,jj;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                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; siz0[jj]+=siz0[ii];
                        }else if(rank0[ii]==rank0[jj]){
                            par0[ii]=jj; rank0[jj]++;siz0[jj]+=siz0[ii];
                        }else{
                            par0[jj]=ii;siz0[ii]+=siz0[jj];
                        }
                    }
                }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;siz0[jj]+=siz0[ii];
                        }else if(rank0[ii]==rank0[jj]){
                            par0[ii]=jj; rank0[jj]++;siz0[jj]+=siz0[ii];
                        }else{
                            par0[jj]=ii;siz0[ii]+=siz0[jj];
                        }
                    }
                }else if(p[i][j]==3){
                    return 0;
                }else{
                    ii=find(i,par0); jj=find(j,par0);
                    if(ii==jj)return 0;
                }
            }
        }
        
        //Go over all components of size 3 again
        int[][] comp=new int[N][2];
        for (int i = 0; i < N; i++) {
            comp[i][0]=-1; comp[i][1]=-1;
        }
        for (int i = 0; i < N; i++) {
            ii=find(i,par0);
            if(siz0[ii]==3){
                if(i!=ii){
                    if(comp[ii][0]==-1){
                        comp[ii][0]=i;
                    }else{
                        comp[ii][1]=i;
                    }
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            if(comp[i][0]!=-1){
                int a=p[i][comp[i][0]];
                int x=p[i][comp[i][1]];
                int c=p[comp[i][0]][comp[i][1]];
                if(a!=x || x!=c || c!=a){
                    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; 
        int prevo=0;//Completes the cycle
        int save=0;
        for (Pair q: leads) {
            
            if(prevl!=q.l0){
                if(prevl!=-1){
                    b[prevv][prevo]=1;b[prevo][prevv]=1;
                } 
                b[q.v][q.l0]=1; b[q.l0][q.v]=1;
                prevl=q.l0; prevo=q.v; 
                
            }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: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4