oj.uz

Submission #301425

# Submission time Handle Problem Language Result Execution time Memory
301425 2020-09-17T23:23:00 Z KWang31 Connecting Supertrees (IOI20_supertrees) Java 11
21 / 100
 557 ms 57516 KB 
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++) {
            ii=find(i,par1);
            if(!done[ii]){
                jj=find(ii,par0);
                
               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
        done=new boolean[N];
        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
            }
            //I want to insert every root of each par1 component exactly once
            if(!done[ii]){
                leads.add(new Pair(ii,find(ii,par0)));
                done[ii]=true;
            }
            
        }
        
        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
        for (int i = 0; i < N; i++) {
            b[i][i]=0;
        }
        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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10128 KB Output is correct
2 Correct 85 ms 10240 KB Output is correct
3 Correct 86 ms 9964 KB Output is correct
4 Correct 85 ms 10144 KB Output is correct
5 Correct 85 ms 10192 KB Output is correct
6 Correct 188 ms 16292 KB Output is correct
7 Correct 482 ms 57516 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10128 KB Output is correct
2 Correct 85 ms 10240 KB Output is correct
3 Correct 86 ms 9964 KB Output is correct
4 Correct 85 ms 10144 KB Output is correct
5 Correct 85 ms 10192 KB Output is correct
6 Correct 188 ms 16292 KB Output is correct
7 Correct 482 ms 57516 KB Output is correct
8 Correct 88 ms 10328 KB Output is correct
9 Correct 90 ms 10296 KB Output is correct
10 Correct 87 ms 10288 KB Output is correct
11 Correct 94 ms 10124 KB Output is correct
12 Correct 204 ms 16000 KB Output is correct
13 Correct 529 ms 56216 KB Output is correct
14 Correct 91 ms 10104 KB Output is correct
15 Correct 109 ms 9892 KB Output is correct
16 Correct 113 ms 10960 KB Output is correct
17 Correct 170 ms 19080 KB Output is correct
18 Correct 82 ms 10060 KB Output is correct
19 Correct 82 ms 10352 KB Output is correct
20 Correct 343 ms 28444 KB Output is correct
21 Correct 476 ms 56840 KB Output is correct
22 Correct 555 ms 56652 KB Output is correct
23 Correct 496 ms 56016 KB Output is correct
24 Correct 557 ms 57420 KB Output is correct
25 Correct 210 ms 19872 KB Output is correct
26 Correct 196 ms 20232 KB Output is correct
27 Correct 497 ms 56376 KB Output is correct
28 Correct 544 ms 56872 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10376 KB Output is correct
2 Correct 88 ms 10460 KB Output is correct
3 Correct 83 ms 10356 KB Output is correct
4 Correct 85 ms 10140 KB Output is correct
5 Incorrect 95 ms 10228 KB Too few ways to get from 0 to 1, should be 2 found 1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10408 KB Output is correct
2 Incorrect 82 ms 10340 KB Too few ways to get from 0 to 1, should be 2 found 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10128 KB Output is correct
2 Correct 85 ms 10240 KB Output is correct
3 Correct 86 ms 9964 KB Output is correct
4 Correct 85 ms 10144 KB Output is correct
5 Correct 85 ms 10192 KB Output is correct
6 Correct 188 ms 16292 KB Output is correct
7 Correct 482 ms 57516 KB Output is correct
8 Correct 88 ms 10328 KB Output is correct
9 Correct 90 ms 10296 KB Output is correct
10 Correct 87 ms 10288 KB Output is correct
11 Correct 94 ms 10124 KB Output is correct
12 Correct 204 ms 16000 KB Output is correct
13 Correct 529 ms 56216 KB Output is correct
14 Correct 91 ms 10104 KB Output is correct
15 Correct 109 ms 9892 KB Output is correct
16 Correct 113 ms 10960 KB Output is correct
17 Correct 170 ms 19080 KB Output is correct
18 Correct 82 ms 10060 KB Output is correct
19 Correct 82 ms 10352 KB Output is correct
20 Correct 343 ms 28444 KB Output is correct
21 Correct 476 ms 56840 KB Output is correct
22 Correct 555 ms 56652 KB Output is correct
23 Correct 496 ms 56016 KB Output is correct
24 Correct 557 ms 57420 KB Output is correct
25 Correct 210 ms 19872 KB Output is correct
26 Correct 196 ms 20232 KB Output is correct
27 Correct 497 ms 56376 KB Output is correct
28 Correct 544 ms 56872 KB Output is correct
29 Correct 88 ms 10376 KB Output is correct
30 Correct 88 ms 10460 KB Output is correct
31 Correct 83 ms 10356 KB Output is correct
32 Correct 85 ms 10140 KB Output is correct
33 Incorrect 95 ms 10228 KB Too few ways to get from 0 to 1, should be 2 found 1
34 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10128 KB Output is correct
2 Correct 85 ms 10240 KB Output is correct
3 Correct 86 ms 9964 KB Output is correct
4 Correct 85 ms 10144 KB Output is correct
5 Correct 85 ms 10192 KB Output is correct
6 Correct 188 ms 16292 KB Output is correct
7 Correct 482 ms 57516 KB Output is correct
8 Correct 88 ms 10328 KB Output is correct
9 Correct 90 ms 10296 KB Output is correct
10 Correct 87 ms 10288 KB Output is correct
11 Correct 94 ms 10124 KB Output is correct
12 Correct 204 ms 16000 KB Output is correct
13 Correct 529 ms 56216 KB Output is correct
14 Correct 91 ms 10104 KB Output is correct
15 Correct 109 ms 9892 KB Output is correct
16 Correct 113 ms 10960 KB Output is correct
17 Correct 170 ms 19080 KB Output is correct
18 Correct 82 ms 10060 KB Output is correct
19 Correct 82 ms 10352 KB Output is correct
20 Correct 343 ms 28444 KB Output is correct
21 Correct 476 ms 56840 KB Output is correct
22 Correct 555 ms 56652 KB Output is correct
23 Correct 496 ms 56016 KB Output is correct
24 Correct 557 ms 57420 KB Output is correct
25 Correct 210 ms 19872 KB Output is correct
26 Correct 196 ms 20232 KB Output is correct
27 Correct 497 ms 56376 KB Output is correct
28 Correct 544 ms 56872 KB Output is correct
29 Correct 88 ms 10376 KB Output is correct
30 Correct 88 ms 10460 KB Output is correct
31 Correct 83 ms 10356 KB Output is correct
32 Correct 85 ms 10140 KB Output is correct
33 Incorrect 95 ms 10228 KB Too few ways to get from 0 to 1, should be 2 found 1
34 Halted 0 ms 0 KB -