Submission #301391

#TimeUsernameProblemLanguageResultExecution timeMemory
301391KWang31Connecting Supertrees (IOI20_supertrees)Java
0 / 100
81 ms10460 KiB
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 = 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; }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; 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...