Submission #301179

#	Time	Username	Problem	Language	Result	Execution time	Memory
301179		amiratou	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	269 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1005;
#define sz(x) (int)(x.size())

int par_p[MX],par_s[MX];
vector<int> bucket[MX];
bitset<MX> vis;
int find_p(int i){
	if(par_p[i]==i)return i;
	return par_p[i]=find_p(par_p[i]);
}
int find_s(int i){
	if(par_s[i]==i)return i;
	return par_s[i]=find_s(par_s[i]);
}
void Union_s(int i,int j){
	i=find_s(i),j=find_s(j);
	if(i!=j)par_s[i]=j;
}
void Union_p(int i,int j){
	i=find_p(i),j=find_p(j);
	if(i!=j)par_p[i]=j;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; ++i)
		for (int j = i+1; j < n; ++j)
			if(p[i][j]==3)return 0;
	vector<vector<int> > ans(n);
	for (int i = 0; i < n; ++i){
		par_p[i]=par_s[i]=i;
		ans[i].resize(n);
	}
	for (int i = 0; i < n; ++i)
		for (int j = i+1; j < n; ++j)
		{
			if(p[i][j]==2)
				Union_s(i,j);
			else if(p[i][j]==1)Union_p(i,j);
		}
	for (int i = 0; i < n; ++i)
		if(!vis[find_p(i)]){
			vis[find_p(i)]=1;
			bucket[find_s(i)].push_back(find_p(i));
		}
	for (int i = 0; i < n; ++i)
	{
		//cerr<<sz(bucket[i])<<"-";
		if(sz(bucket[i])==2)return 0;
		if(sz(bucket[i])<=1)continue;
		for (int j = 0; j < sz(bucket[i]); ++j)
			ans[bucket[i][j]][bucket[i][(j+1)%sz(bucket[i])]]=ans[bucket[i][(j+1)%sz(bucket[i])]][bucket[i][j]]=1;
	}
	for (int i = 0; i < n; ++i)
		if(find_p(i)!=i)ans[find_p(i)][i]=ans[i][find_p(i)]=1;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i+1; j < n; ++j)
		{
			//cerr<<p[i][j]<<" ";
			if((p[i][j]==0) && (find_s(find_p(i))==find_s(find_p(j))))return 0;
			if((p[i][j]==2) && ((find_p(i)==find_p(j))|| (find_s(find_p(i))!=find_s(find_p(j)))))return 0;
			if((p[i][j]==1) && (find_p(i)!=find_p(j)))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