Submission #377868

#	Time	Username	Problem	Language	Result	Execution time	Memory
377868		KoD	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	338 ms	26108 KiB

supertrees

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

template <class T>
using Vec = std::vector<T>;

struct DSU {
	Vec<int> par;
	DSU(const int n): par(n, -1) { }
	int find(const int u) {
		return par[u] < 0 ? u : par[u] = find(par[u]);
	}
	void merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (par[x] > par[y]) std::swap(x, y);
		par[x] += par[y];
		par[y] = x;
	}
};

int construct(Vec<Vec<int>> p) {
	const auto n = (int) p.size();
	std::array<Vec<std::pair<int, int>>, 3> pair;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (p[i][j] == 3) {
				return 0;
			}
			pair[p[i][j]].emplace_back(i, j);
		}
	}
	DSU all(n), one(n);
	for (int k = 1; k <= 2; ++k) {
		for (const auto [x, y]: pair[k]) {
			all.merge(x, y);
		}
	}
	for (const auto [x, y]: pair[1]) {
		one.merge(x, y);
	}
	for (const auto [x, y]: pair[0]) {
		if (all.find(x) == all.find(y)) {
			return 0;
		}
	}
	for (const auto [x, y]: pair[2]) {
		if (one.find(x) == one.find(y)) {
			return 0;
		}
	}
	Vec<Vec<int>> ret(n, Vec<int>(n));
	const auto add_edge = [&](const int x, const int y) {
		ret[x][y] = ret[y][x] = 1;
	};
	for (int i = 0; i < n; ++i) {
		const auto j = one.find(i);
		if (i != j) {
			add_edge(i, j);
		}
	}
	std::map<int, std::set<int>> cycle;
	for (const auto [x, y]: pair[2]) {
		cycle[all.find(x)].insert(one.find(x));
		cycle[all.find(y)].insert(one.find(y));
	}
	for (const auto [_, s]: cycle) {
		Vec<int> v(s.begin(), s.end());
		const auto k = (int) v.size();
		if (k == 1 || k == 2) {
			return 0;
		}
		for (int i = 0; i < k; ++i) {
			add_edge(v[i], v[(i + 1) % k]);
		}
	}
	build(ret);
	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