Submission #1182889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182889		boclobanchat	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	125 ms	26188 KiB

supertrees

#include"supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
vector<int> ds[MAXN],vi;
bool ck[MAXN],vis[MAXN];
int dsu[MAXN];
void dfs(int i)
{
	ck[i]=true,vi.push_back(i);
	for(auto v:ds[i]) if(!ck[v]) dfs(v);
}
int root(int i)
{
	if(!dsu[i]) return i;
	return dsu[i]=root(dsu[i]);
}
void merge(int i,int j)
{
	if((i=root(i))==(j=root(j))) return ;
	dsu[j]=i;
}
int construct(vector< vector<int> > p)
{
	int n=p.size();
	vector< vector<int> > ans(n);
	for(int i=0;i<n;i++) ans[i].resize(n);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++)
	{
		if(p[i][j]) ds[i].push_back(j);
		if(p[i][j]==3) return 0;
	}
	for(int i=0;i<n;i++) if(!ck[i])
	{
		vi.clear();
		dfs(i);
		bool ck=true;
		for(auto v:vi) for(auto u:vi)
		{
			if(!p[v][u]) return 0;
			ck&=(p[v][u]==1);
		}
		if(ck) for(int j=1;j<vi.size();j++) ans[vi[0]][vi[j]]=ans[vi[j]][vi[0]]=1;
		else
		{
			vector<int> vp;
			for(int j=0;j<vi.size();j++) for(int k=0;k<vi.size();k++) if(p[vi[j]][vi[k]]==1) merge(vi[j],vi[k]);
			for(int j=0;j<vi.size();j++) for(int k=0;k<vi.size();k++) if((root(vi[j])==root(vi[k]))^(p[vi[j]][vi[k]]==1)) return 0;
			for(int j=0;j<vi.size();j++) if(!vis[vi[j]])
			{
				for(int k=0;k<vi.size();k++) if(root(vi[j])==root(vi[k])&&j!=k) ans[vi[k]][vi[j]]=ans[vi[j]][vi[k]]=1,vis[vi[k]]=true;
				vp.push_back(vi[j]),vis[vi[j]]=true;
			}
			if(vp.size()==2) return 0;
			for(int j=0;j<vp.size();j++) if(j==vp.size()-1) ans[vp[j]][vp[0]]=ans[vp[0]][vp[j]]=1;
			else ans[vp[j]][vp[j+1]]=ans[vp[j+1]][vp[j]]=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