Submission #832270

#	Time	Username	Problem	Language	Result	Execution time	Memory
832270		Johann	슈퍼트리 잇기 (IOI20_supertrees)	C++14	56 / 100	1094 ms	24068 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 (sz(c[2]) && sz(c[3]))
				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;

				vvi cycle;
				vi C2(all(c[2]));
				while (!C2.empty())
				{
					int u = C2.back();
					C2.pop_back();
					cycle.push_back({u});
					int end = sz(C2);
					for (int i = 0; i < end;)
					{
						int w = C2[i];
						if (p[u][w] == 2)
							++i;
						else if (p[u][w] == 1)
						{
							cycle.back().push_back(w);
							swap(C2[i], C2[--end]);
							C2.pop_back();
						}
					}
				}

				// checks
				if (sz(cycle) <= 1)
					return 0;
				for (int i = 0; i < sz(cycle); ++i)
				{
					for (int u : cycle[i])
						for (int w : cycle[i])
							if (p[u][w] != 1)
								return 0;
					for (int j = i + 1; j < sz(cycle); ++j)
						for (int u : cycle[i])
							for (int w : cycle[j])
								if (p[u][w] != 2)
									return 0;
				}

				// build
				int last = v;
				for (int i = 0; i < sz(cycle); ++i)
				{
					int u = cycle[i][0];
					ans[last][u] = ans[u][last] = 1;
					last = u;
					for (int j = 1; j < sz(cycle[i]); ++j)
						ans[u][cycle[i][j]] = ans[cycle[i][j]][u] = 1;
				}
				ans[last][v] = ans[v][last] = 1;
			}
		}
	}

	build(ans);
	return 1;
}

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