Submission #832990

#	Time	Username	Problem	Language	Result	Execution time	Memory
832990		Johann	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	203 ms	22128 KiB

supertrees

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

typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int construct(std::vector<std::vector<int>> p)
{
	int N = p.size();
	vi comp(N, -1);

	vvi ans(N, vi(N, 0));
	for (int v = 0; v < N; ++v)
	{
		if (comp[v] == -1)
		{
			vvi c(4);
			comp[v] = v;
			for (int u = 0; u < N; ++u)
			{
				if (p[v][u] == 0 || u == v)
					continue;
				if (comp[u] != -1)
					return 0;
				comp[u] = v;
				c[p[v][u]].push_back(u);
			}

			if (!c[3].empty())
				return 0;

			for (int u : c[1])
			{
				ans[v][u] = ans[u][v] = 1;
				for (int w = 0; w < N; ++w)
					if (comp[w] != comp[u] && p[u][w] > 0)
						return 0;
				for (int w : c[1])
					if (p[u][w] != 1)
						return 0;
				for (int w : c[2])
					if (p[u][w] != 2)
						return 0;
				for (int w : c[3])
					if (p[u][w] != 3)
						return 0;
			}

			if (!c[2].empty())
			{
				for (int u : c[2])
					for (int w = 0; w < N; ++w)
						if (comp[w] != comp[u] && p[u][w] > 0)
							return 0;

				int last = v;
				vi belongs(sz(c[2]), -1);
				for (int i = 0; i < sz(c[2]); ++i)
				{
					int u = c[2][i];
					if (belongs[i] == -1)
					{
						ans[last][u] = ans[u][last] = 1;
						last = u;
						belongs[i] = u;
					}
					for (int j = i + 1; j < sz(c[2]); ++j)
					{
						int w = c[2][j];
						if (p[u][w] == 1)
						{
							if (belongs[j] != -1)
							{
								if (belongs[j] != belongs[i])
									return 0;
							}
							else
							{
								belongs[j] = belongs[i];
								ans[w][u] = ans[u][w] = 1;
							}
						}
						else if (p[u][w] == 2)
						{
							if (belongs[i] == belongs[j])
								return 0;
						}
						else
							return 0;
					}
				}
				if (ans[v][last])
					return 0;
				ans[v][last] = ans[last][v] = 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