Submission #530749

#	Time	Username	Problem	Language	Result	Execution time	Memory
530749		ToroTN	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	221 ms	32060 KiB

supertrees

#include<bits/stdc++.h>
using namespace std;
#include "supertrees.h"
#include <vector>
int d[1005][1005],p1[1005],p2[1005],type,u,ans[1005][1005],vis[1005],cnt;
vector<int> v[1005],g[1005],kawin;
set<int> s[1005];
queue<int> q;
int f1(int a)
{
	if(p1[a]==a)
	{
		return a;
	}
	return p1[a]=f1(p1[a]);
}
void un1(int b,int c)
{
	p1[f1(b)]=f1(c);
}
int f2(int a)
{
	if(p2[a]==a)
	{
		return a;
	}
	return p2[a]=f2(p2[a]);
}
void un2(int b,int c)
{
	p2[f2(b)]=f2(c);
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			d[i][j]=p[i-1][j-1];
		}
		p1[i]=i;
		p2[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(d[i][j]>=1)
			{
				un1(i,j);
			}
			if(d[i][j]==1)
			{
				un2(i,j);
			}
		}
	}
	/*for(int i=1;i<=n;i++)
	{
		printf("%d %d\n",p1[i],p2[i]);
	}*/
	type=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(f1(i)!=f1(j))
			{
				if(d[i][j]!=0)
				{
					type=-1;
				}
			}else
			{
				if(f2(i)==f2(j))
				{
					if(d[i][j]!=1)
					{
						type=-1;
					}
				}else
				{
					if(d[i][j]!=2)
					{
						type=-1;
					}
				}
			}
		}
	}
	memset(vis,-1,sizeof vis);
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==-1)
		{
			cnt=0;
			q.push(i);
			vis[i]=0;
			while(!q.empty())
			{
				u=q.front();
				++cnt;
				q.pop();
				for(int i=1;i<=n;i++)
				{
					if(d[u][i]==2)
					{
						if(vis[i]==-1)
						{
							vis[i]=0;
							q.push(i);
						}
					}
				}
			}
			if(cnt==2)
			{
				type=-1;
			}
		}
	}
	//printf("%d\n",type);
	for(int i=1;i<=n;i++)
	{
		v[f2(i)].push_back(i);
		s[f1(i)].insert(f2(i));
		//g[f1(i)].push_back(f2(i));
		//printf("%d %d\n",f1(i),f2(i));
	}
	/*printf("9holo\n");
	for(auto it=s[4].begin();it!=s[4].end();it++)
	{
		printf("%d ",*it);
	}
	printf("\n");*/
	for(int i=1;i<=n;i++)
	{
		//printf("atittarn=%d\n",i);
		for(auto it=s[i].begin();it!=s[i].end();it++)
		{
			//printf("%d ",*it);
			g[i].push_back(*it);
		}
		//printf("\n");
		/*for(int j=0;j<g[i].size();j++)
		{
			printf("%d ",g[i][j]);
		}
		printf("\n");*/
	}
	for(int i=1;i<=n;i++)
	{
		u=i;
		//printf("%d\n",i);
		for(int j=0;j<(int)v[i].size();j++)
		{
			//printf("%d ",v[i][j]);
			if(v[i][j]!=i)
			{
				ans[u][v[i][j]]=1;
				ans[v[i][j]][u]=1;
				u=v[i][j];
			}
		}
		//printf("\n");
		if(g[i].size()>=2)
		{
			for(int j=0;j<(int)g[i].size()-1;j++)
			{
				ans[g[i][j]][g[i][j+1]]=1;
				ans[g[i][j+1]][g[i][j]]=1;
			}
			ans[g[i][0]][g[i][g[i].size()-1]]=1;
			ans[g[i][g[i].size()-1]][g[i][0]]=1;
		}
	}
	/*for(int i=1;i<=n;i++)
	{
		ans[i][i]=1;
	}*/
	for(int i=1;i<=n;i++)
	{
		kawin.clear();
		for(int j=1;j<=n;j++)
		{
			kawin.push_back(ans[i][j]);
		}
		answer.push_back(kawin);
	}
	if(type==-1)
	{
		return 0;
	}
	build(answer);
	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