Submission #1239472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239472		Muhammad_Aneeq	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	121 ms	22284 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int const N=1010;
int par[N]={};
int comp[N]={};
int ways[N]={};
vector<int>ch[N]={},nei[N]={};
bool stk[N]={};
vector<vector<int>>ans;
int root(int n)
{
	return (n==par[n]?n:par[n]=root(par[n]));
}
void merge(int u,int v)
{
	u=root(u);
	v=root(v);
	if (u==v)
		return;
	ans[u][v]=ans[v][u]=1;
	par[v]=u;
	ch[u].push_back(v);
}
vector<int>z;
void get(int x)
{
	z.push_back(x);
	for (auto i:ch[x])
		get(i);
}
void dfs(int u)
{
	ways[u]++;
	if (ways[u]>3)
		return;
	stk[u]=1;
	for (auto i:nei[u])
	{
		if (stk[i]) continue;
		dfs(i);
	}
	stk[u]=0;
}
int construct(vector<vector<int>> p)
{
	int n=p.size();
	ans=vector<vector<int>>(n,vector<int>(n,0));
	for (int i=0;i<n;i++)
		par[i]=i;
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
			if (p[i][j]==1)
				merge(i,j);
	for (int i=0;i<n;i++)
	{
		set<int>s;
		for (int j=0;j<n;j++)
		{
			if (p[i][j]>1)
				s.insert(p[i][j]);
		}
		if (s.size()>1)
			return 0;
	}
	for (int i=0;i<n;i++)
	{
		if (par[i]==i)
		{
			z={};
			get(i);
		}
	}
	for (int i=0;i<n;i++)
	{
		if (root(i)==i)
		{
			// cout<<i<<endl;
			set<int>s;
			int mx=0;
			for (int j=0;j<n;j++)
			{
				mx=max(mx,p[i][j]);
				if (p[i][j])
					s.insert(root(j));
			}
			vector<int>g={begin(s),end(s)};
			if (mx==1)
				continue;
			int sz=g.size();
			if (mx+1>sz)
				return 0;
			for (auto i:g)
				merge(g[0],i);
			for (int j=0;j<sz;j++)
				ans[g[j]][g[(j+1)%sz]]=ans[g[(j+1)%sz]][g[j]]=1;
			if (mx==3)
				ans[g.back()][g[1]]=ans[g[1]][g.back()]=1;
		}
	}
	for (int i=0;i<n;i++)
	{
		for (int j=i+1;j<n;j++)
		{
			if (ans[i][j])
			{
				nei[i].push_back(j);
				nei[j].push_back(i);
			}
		}
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<n;j++)
			ways[j]=0;
		dfs(i);
		for (int j=0;j<n;j++)
		{
			if (ways[j]!=p[i][j])
				return 0;
		}
	}
	build(ans);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4