Submission #313750

#	Time	Username	Problem	Language	Result	Execution time	Memory
313750		Jasiekstrz	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	278 ms	30328 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#define fi first
#define se second
using namespace std;
vector<int> e1[1010];
vector<int> e2[1010];
vector<int> sp[1010];
int g[1010];
bool vis1[1010];
bool vis2[1010];
vector<vector<int>> ans;
vector<vector<int>> p2;
int construct(vector<vector<int>> p)
{
	int n=p.size(),m,i,j;
	ans=vector<vector<int>>(n);
	for(i=0;i<n;i++)
		ans[i]=vector<int>(n);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			ans[i][j]=0;
			if(p[i][j]==1)
				e1[i].push_back(j);
			if(p[i][j]==3 || p[i][j]!=p[j][i] || p[i][i]!=1)
				return 0;
		}
	}
	for(i=0,j=0;i<n;i++)
	{
		if(vis1[i])
			continue;
		for(auto v:e1[i])
		{
			if(vis1[v])
				return 0;
			vis1[v]=true;
			g[v]=j;
			sp[j].push_back(v);
		}
		for(auto v1:sp[j])
		{
			if(e1[v1].size()!=sp[j].size())
				return 0;
			for(auto v2:sp[j])
			{
				if(p[v1][v2]!=1)
					return 0;
			}
		}
		for(size_t it=1;it<sp[j].size();it++)
			ans[sp[j][it-1]][sp[j][it]]=ans[sp[j][it]][sp[j][it-1]]=1;
		j++;
	}
	m=j;
	p2=vector<vector<int>>(m);
	for(i=0;i<m;i++)
		p2[i]=vector<int>(m);
	for(i=0;i<m;i++)
	{
		for(j=0;j<m;j++)
			p2[i][j]=0;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(p[i][j]==2)
				p2[g[i]][g[j]]=1;
		}
	}
	for(i=0;i<m;i++)
	{
		for(j=0;j<m;j++)
		{
			if(i==j)
				p2[i][j]=1;
			if(p2[i][j]==1)
				e2[i].push_back(j);
		}
	}
	for(i=0;i<m;i++)
	{
		if(vis2[i])
			continue;
		vector<int> tmp;
		for(auto v:e2[i])
		{
			if(vis2[v])
				return 0;
			vis2[v]=true;
			tmp.push_back(v);
		}
		for(auto v1:tmp)
		{
			for(auto vv1:sp[v1])
			{
				int xd=0;
				for(j=0;j<n;j++)
					xd+=(p[vv1][j]==2);
				for(auto v2:tmp)
				{
					if(v1==v2)
						continue;
					for(auto vv2:sp[v2])
					{
						xd--;
						if(p[vv1][vv2]!=2)
							return 0;
					}
				}
				if(xd!=0)
					return 0;
			}
		}
		for(size_t it=1;it<tmp.size();it++)
			ans[sp[tmp[it-1]][0]][sp[tmp[it]][0]]=ans[sp[tmp[it]][0]][sp[tmp[it-1]][0]]=1;
		if(tmp.size()>1)
			ans[sp[tmp.back()][0]][sp[tmp[0]][0]]=ans[sp[tmp[0]][0]][sp[tmp.back()][0]]=1;
		if(tmp.size()==2)
			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