Submission #1239466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239466		MuhammadSaram	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	118 ms	22200 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int construct(vector<vector<int>> p)
{
	int n=p.size();
	bool vis[n]={};
	vector<vector<int>> vv;
	for (int i=0;i<n;i++)
	{
		if (vis[i]) continue;
		vis[i]=1;
		vector<int> v1;
		for (int j=i;j<n;j++)
			if (p[i][j])
				v1.push_back(j), vis[j]=1;
		vv.push_back(v1);
	}
	for (int i=0;i<(int)vv.size();i++)
		for (int j=i;j<(int)vv.size();j++)
		{
			for (int x:vv[i])
				for (int y:vv[j])
					if ((p[x][y]>0)!=(i==j))
						return 0;
		}
	for (int i=0;i<n;i++) vis[i]=0;
	vector<vector<int>> ans(n,vector<int>(n));
	for (auto v:vv)
	{
		int mx=0,m=v.size();
		for (int i:v)
			for (int j:v) mx=max(mx,p[i][j]);
		if(mx==3) return 0;
		if (mx==1)
		{
			for (int j=0;j+1<m;j++)
				ans[v[j]][v[j+1]]=ans[v[j+1]][v[j]]=1;
			continue;
		}
		vector<vector<int>> v2;
		for (int i=0;i<m;i++)
		{
			if (vis[v[i]]) continue;
			vector<int> v3;
			for (int j=i;j<m;j++)
				if (p[v[i]][v[j]]==1)
					v3.push_back(v[j]), vis[v[j]]=1;
			v2.push_back(v3);
		}
		m=v2.size();
		for (int i=0;i<m;i++)
			for (int j=i;j<m;j++)
				for (int x:v2[i])
					for (int y:v2[j])
						if ((i==j)!=(p[x][y]==1))
							return 0;
		if (m<=2) return 0;
		for (int i=0;i<m;i++)
		{
			ans[v2[i][0]][v2[(i+1)%m][0]]=1,ans[v2[(i+1)%m][0]][v2[i][0]]=1;
			for (int j:v2[i])
				ans[v2[i][0]][j]=ans[j][v2[i][0]]=(j!=v2[i][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