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;
}
}
# |
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 |
# |
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 |
# |
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 |
- |
# |
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 |
- |
# |
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 |
- |
# |
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 |
- |