Submission #303009

#	Time	Username	Problem	Language	Result	Execution time	Memory
303009		tutis	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	277 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (p[i][j] == 3)
				return 0;
	int C[n];
	iota(C, C + n, 0);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (p[i][j] == 1 && C[i] != C[j])
			{
				int x = C[i];
				for (int a = 0; a < n; a++)
					if (C[a] == x)
						C[a] = C[j];
			}
		}
	vector<vector<int>>ans(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++)
		if (C[i] != i)
			ans[i][C[i]] = ans[C[i]][i] = 1;
	int X[n];
	for (int i = 0; i < n; i++)
		if (C[i] == i)
			X[i] = i;
		else
			X[i] = -1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (p[i][j] == 2 && X[i] != X[j] && X[i] != -1 && X[j] != -1)
			{
				int x = X[i];
				for (int a = 0; a < n; a++)
					if (X[a] == x)
						X[a] = X[j];
			}
		}
	for (int i = 0; i < n; i++)
	{
		vector<int>x;
		for (int j = 0; j < n; j++)
			if (X[j] == i)
				x.push_back(j);
		if (x.size() > 1)
		{
			if (x.size() == 2)
				return 0;
			int a = x.back();
			for (int b : x)
			{
				ans[a][b] = ans[b][a] = 1;
				a = b;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (p[i][j] == 0 && X[C[i]] == X[C[j]])
				return 0;
			if (p[i][j] == 1 && C[i] != C[j])
				return 0;
			if (p[i][j] == 2 && (X[C[i]] != X[C[j]] || C[i] == C[j]))
				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