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
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 |
Incorrect |
82 ms |
10228 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
10228 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
10236 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
10352 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
10228 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
10228 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
