Submission #377862

#	Time	Username	Problem	Language	Result	Execution time	Memory
377862		KoD	슈퍼트리 잇기 (IOI20_supertrees)	C++17	0 / 100	1 ms	364 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::set<int> leader;
	for (int i = 0; i < n; ++i) {
		leader.insert(one.find(i));
	}
	Vec<int> cycle(leader.begin(), leader.end());
	const auto k = (int) cycle.size();
	for (int i = 0; i < k; ++i) {
		add_edge(cycle[i], cycle[(i + 1) % k]);
	}
	build(ret);
	return 1;
}

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