Submission #1220155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220155		Malix	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	140 ms	22248 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n;
vi p,s;
vii a;

int parent(int x){
	if(p[x]==x)return x;
	return p[x]=parent(p[x]);
}

void merge(int x,int y){
	x=parent(x);
	y=parent(y);
	if(x==y)return;
	if(s[x]<s[y])swap(x,y);
	s[x]+=s[y];
	p[y]=x;
}

int construct(std::vector<std::vector<int>> R) {
	n=R.size();
	REP(i,0,n)REP(j,0,n)if(R[i][j]==3)return 0;
	vii ans(n,vi(n,0));
	p.resize(n);s.resize(n,1);
	REP(i,0,n)p[i]=i;
	REP(i,0,n)REP(j,0,n)if(i!=j&&R[i][j]==1&&parent(i)!=parent(j)){
		merge(i,j);
		ans[i][j]=1;
		ans[j][i]=1;
	}
	REP(i,0,n)if(R[parent(i)]!=R[i])return 0;
	REP(i,0,n)REP(j,0,n)if(parent(i)==parent(j)&&R[i][j]==0)return 0;
	a.resize(n);
	REP(i,0,n)a[parent(i)].PB(i);
	REP(i,0,n)sort(all(a[i]));
	vi vis(n,0),cnt(n,0);
	REP(i,0,n)REP(j,0,n)if(R[i][j]==2)cnt[i]++;
	REP(i,0,n)if(cnt[i]==1)return 0;
	REP(i,0,n)if(!vis[i]&&a[i].size()){
		if(cnt[i]==0)continue;
		set<int> st,st2;
		int x=parent(a[i][0]);
		st.insert(x);
		REP(j,0,n)if(R[x][j]==2)st.insert(parent(j));
		for(auto u:st){
			if(vis[u])return 0;
			vis[u]=1;
			for(auto v:a[u])st2.insert(v);
		}
		int sz=st2.size();
		vi arr;
		for(auto u:st){
			if(cnt[u]!=sz-a[u].size())return 0;
			REP(j,0,n)if(R[u][j]==2&&st2.count(j)==0)return 0;
			arr.PB(u);
		}
		int y=arr.size();
		REP(i,0,y){
			ans[arr[i]][arr[(i+1)%y]]=1;
			ans[arr[(i+1)%y]][arr[i]]=1;
		}
	}
	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