Submission #304147

#	Time	Username	Problem	Language	Result	Execution time	Memory
304147		QAQAutoMaton	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	319 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <vector>
struct dsu{
	int fa[1005];
	void init(int n){
		for(int i=0;i<n;++i)fa[i]=i;
	}
	int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
	void merge(int x,int y){fa[find(x)]=find(y);}
	int rt(int x){return fa[x]==x;}
}a,b;
int query(int x,int y){
	if(a.find(x)==a.find(y))return 1;
	if(b.find(a.find(x))==b.find(a.find(y)))return 2;
	return 0;
}
std::vector<int> al[1005],bl[1005];
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	a.init(n);b.init(n);
	std::vector<std::vector<int>> ans(n,std::vector<int>(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=i+1;j<n;++j)if(p[i][j]==1){a.merge(i,j);}
	for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)if(p[i][j]==2){b.merge(a.find(i),a.find(j));}
	for(int i=0;i<n;++i)for(int j=1;j<n;++j){
		if(p[i][j]!=query(i,j))return 0;
	}
	for(int i=0;i<n;++i){
		al[a.find(i)].emplace_back(i);
		if(a.rt(i)){
			bl[b.find(i)].emplace_back(i);
		}
	}
	for(int i=0;i<n;++i)if(a.rt(i)){
		int m=al[i].size();
		for(int j=0;j+1<m;++j){
			int x=al[i][j],y=al[i][j+1];
			ans[x][y]=ans[y][x]=1;
		}
	}
	for(int i=0;i<n;++i){
		if(a.rt(i) && b.rt(i)){
			if(bl[i].size()==1)continue;
			if(bl[i].size()==2)return 0;
			int m=bl[i].size();
			for(int j=0;j<m;++j){
				int x=bl[i][j],y=j==m-1?bl[i][0]:bl[i][j+1];
				ans[x][y]=ans[y][x]=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