Submission #300489

#	Time	Username	Problem	Language	Result	Execution time	Memory
300489		20160161simone	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	282 ms	23928 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10;
int f[N][4];
int Find(int x,int op){
	if(f[x][op]==x) return x;
	else return f[x][op]=Find(f[x][op],op);
}
void Union(int x,int y,int op){
	x=Find(x,op),y=Find(y,op);
	if(x==y) return;
	f[y][op]=x;
}
int rol[N][N],len[N],vis[N][N];

int construct(std::vector<std::vector<int>> p) {
	int n = p.size(),tf=0;
	for(int i=0;i<n;i++) f[i][1]=f[i][2]=i;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]==3) return 0;
			if(p[i][j]==1){
				Union(i,j,1);
				tf=1;
			}
			if(p[i][j]==2){
				Union(i,j,2);
				tf=1;
			}
		}
	}
	vector< vector<int> > ans;
	for(int i=0;i<n;i++){
		vector<int> row;
		for(int j=0;j<n;j++) row.push_back(0);
		ans.push_back(row);
	}
	for(int i=0;i<n;i++){
		int t1=Find(i,1),t2=Find(t1,2);
		if(t1!=t2 && Find(t1,1)==Find(t2,1)){
			f[t1][1]=t2,f[t2][1]=t2;
			t1=t2;
		}
		if(t1!=i){
			ans[t1][i]=ans[i][t1]=1;
		}
		if(t2!=t1){
			if(!vis[t2][t1]) rol[t2][++len[t2]]=t1;
			vis[t2][t1]=1;
		}
	}
	//for(int i=0;i<n;i++) cout<<Find(i,1)<<" "<<Find(i,2)<<endl;
	for(int i=0;i<n;i++){
		if(len[i]){
			if(len[i]==1) return 0;
			rol[i][0]=i;
			for(int j=0;j<len[i];j++){
				ans[ rol[i][j] ][ rol[i][j+1] ]=ans[ rol[i][j+1] ][ rol[i][j] ]=1;
			}
			ans[ rol[i][len[i]] ][i]=ans[i][ rol[i][len[i]] ]=1;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(p[i][j]==0){
				if(Find(i,1)==Find(j,1) || Find(i,2)==Find(j,2)) return 0;
			}
		}
	}

	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:19:19: warning: variable 'tf' set but not used [-Wunused-but-set-variable]
   19 |  int n = p.size(),tf=0;
      |                   ^~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4