Submission #800057

#	Time	Username	Problem	Language	Result	Execution time	Memory
800057		LittleCube	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	166 ms	31980 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> adj, tree, trees, ans;
vector<int> cc, subtree;

void dfs(int u, int r, vector<vector<int>> &adj, vector<int> &cc)
{
	cc[u] = r;
	for (int v = 0; v < n; v++)
		if (adj[u][v] && cc[v] == -1)
			dfs(v, r, adj, cc);
}

int construct(vector<vector<int>> p)
{
	n = p.size();
	adj = tree = ans = vector<vector<int>>(n, vector<int>(n, 0));
	cc = subtree = vector<int>(n, -1);
	trees.resize(n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			adj[i][j] = p[i][j] > 0;
			tree[i][j] = p[i][j] == 1;
			if (p[i][j] == 3)
				return 0;
		}
	for (int i = 0; i < n; i++)
		if (cc[i] == -1)
			dfs(i, i, adj, cc);
	for (int i = 0; i < n; i++)
		if (subtree[i] == -1)
			dfs(i, i, tree, subtree);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (cc[i] != cc[j])
			{
				if (p[i][j] != 0)
					return 0;
			}
			else if (cc[i] == cc[j] && subtree[i] != subtree[j])
			{
				if (p[i][j] != 2)
					return 0;
			}
			else
			{
				if (p[i][j] != 1)
					return 0;
			}
		}
	for (int i = 0; i < n; i++)
		if (subtree[i] != i)
			ans[i][subtree[i]] = ans[subtree[i]][i] = 1;
		else if(subtree[i] == i)
			trees[cc[i]].emplace_back(i);
	for (int i = 0; i < n; i++)
		if(trees[i].size() <= 1)
			continue;
		else if(trees[i].size() == 2)
			return 0;
		else
		{
			int k = trees[i].size();
			for (int j = 0; j < k; j++)
				ans[trees[i][j]][trees[i][(j + 1) % k]] = ans[trees[i][(j + 1) % k]][trees[i][j]] = 1;
		}
	
	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