Submission #301580

#	Time	Username	Problem	Language	Result	Execution time	Memory
301580		Batyr	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	285 ms	26236 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sz(a) (int)a.size()
#define pb push_back
const int maxn=1e3+5;
// head

int n;
int d[maxn];
int b[maxn];
vector<vector<int>> p;
vector<vector<int>> ans;

int ata(int x){
	if(x==d[x]) return x;
	return d[x]=ata(d[x]);
}

int ata2(int x){
	if(x==b[x]) return x;
	return b[x]=ata2(b[x]);
}

int f(vector<int>v){
	if(sz(v)==0) return 1;
	for(int i = 0;i < sz(v);i++) b[v[i]]=v[i];
	for(int i = 0;i < sz(v);i++){
		for(int j = 0;j < i;j++){
			if(p[v[i]][v[j]]==1){
				int x=ata2(v[i]),y=ata2(v[j]);
				if(x != y) b[y]=x;
			}
		}
	}
	vector<int> br[n+1];
	set<int> s;
	for(int i = 0;i < sz(v);i++){
		ata2(v[i]);
		br[b[v[i]]].pb(v[i]);
		s.insert(b[v[i]]);
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < sz(br[i]);j++){
			for(int k = 0;k < j;k++){
				if(p[br[i][j]][br[i][k]]==2) return 0;
			}
			if(j > 0) ans[br[i][j]][br[i][j-1]]=1,ans[br[i][j-1]][br[i][j]]=1;
		}
	}
	if(sz(s)==2) return 0;
	if(sz(s)==1) return 1;
	int fi=-1,ls=-1;
	for(auto i : s){
		if(fi==-1) fi=i;
		if(ls != -1) ans[i][ls]=1,ans[ls][i]=1;
		ls=i;
	}
	ans[ls][fi]=1,ans[fi][ls]=1;
	return 1;
}

int construct(vector<vector<int>> _p) {
	p = _p;
	n = p.size();
	ans.resize(n);
	for(int i = 0;i < n;i++){
		d[i]=i;
		ans[i].resize(n);
	}
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++) if(p[i][j]==3) return 0;
	
	for(int i = 0;i < n;i++){
		for(int j = 0;j < i;j++){
			if(p[i][j]>0){
				int x=ata(i),y=ata(j);
				if(x != y) d[y]=x;
			}
		}
	}
	vector<int>v[n+1];
	for(int i = 0;i < n;i++){
		ata(i);
		v[d[i]].pb(i);
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < sz(v[i]);j++){
			for(int k = 0;k < j;k++){
				if(p[v[i][j]][v[i][k]] == 0) return 0;
			}
		}
	}
	for(int i = 0;i < n;i++){
		int jog = f(v[i]);
		if(jog==0) return 0;
	}
	build(ans);
	return 1;
}

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