Submission #502996

#	Time	Username	Problem	Language	Result	Execution time	Memory
502996		sliviu	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	226 ms	22084 KiB

supertrees

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

using namespace std;

int construct(vector<vector<int>> p) {
	int n = p.size(), cur = 0, bad = 0;
	vector<vector<int>> ans(n, vector<int>(n));
	vector<int> seen(n), solved(n), cycle;
	function<void(int)> dfs = [&](int node) {
		if (bad)
			return;
		seen[node] = cur;
		int c1 = 0, c2 = 0;
		for (int i = 0; i < n; ++i)
			if (i != node) {
				if (p[node][i] == 1)
					++c1;
				else if (p[node][i] == 2)
					++c2;
				else if (p[node][i] == 3)
					bad = 1;
				if (!seen[i] && p[node][i])
					dfs(i);
				if (!p[node][i] && seen[i] == cur)
					bad = 1;
			}
		if (!c1 && c2)
			cycle.emplace_back(node);
		if (!solved[node] && c1) {
			if (c2)
				cycle.emplace_back(node);
			solved[node] = 1;
			int cur = node;
			for (int i = 0; i < n; ++i)
				if (i != node && p[node][i] == 1)
					ans[cur][i] = ans[i][cur] = solved[i] = 1, cur = i;
		}
	};
	for (int i = 0; i < n; ++i)
		if (!seen[i]) {
			cycle.clear();
			++cur;
			dfs(i);
			if (bad)
				return 0;
			if (!cycle.empty()) {
				if (cycle.size() == 2)
					return 0;
				int root = cycle[0], cur = root;
				for (auto x : cycle) {
					if (x != root) {
						ans[cur][x] = ans[x][cur] = 1;
						cur = x;
					}
				}
				ans[cur][root] = ans[root][cur] = 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