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;
return 1;//idc
}
}
/*
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 =1; 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;
}
}
}
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) {
//System.out.println(q.v+" "+q.l0);
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;
}
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);
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;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
77 ms |
10488 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
77 ms |
10488 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
80 ms |
10360 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
80 ms |
10524 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
77 ms |
10488 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
77 ms |
10488 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
