Submission #601095

#	Time	Username	Problem	Language	Result	Execution time	Memory
601095		Temmie	Split the Attractions (IOI19_split)	C++17	18 / 100	121 ms	34148 KiB

split

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

std::vector <int> find_split(int n, int _a, int _b, int _c, std::vector <int> _u, std::vector <int> _v) {
	int m = _u.size();
	std::vector <std::pair <int, int>> s = { { _a, 1 }, { _b, 2 }, { _c, 3 } };
	std::sort(s.begin(), s.end());
	std::vector <int> ans(n, s[2].second);
	std::vector <std::vector <int>> g(n);
	std::vector <std::vector <int>> h(n);
	for (int i = 0; i < m; i++) {
		g[_u[i]].push_back(_v[i]);
		g[_v[i]].push_back(_u[i]);
	}
	std::vector <int> sub(n, 1);
	std::vector <int> dep(n, 0);
	std::vector <int> fur(n, 1 << 30);
	std::vector <bool> vis(n, false);
	std::vector <bool> stop(n, false);
	auto ini = [&] (auto&& self, int node, int par) -> void {
		vis[node] = true;
		for (int x : g[node]) {
			if (!vis[x]) {
				dep[x] = dep[node] + 1;
				self(self, x, node);
				sub[node] += sub[x];
				h[node].push_back(x);
			} else {
				fur[node] = std::min(fur[node], dep[x]);
			}
		}
	};
	ini(ini, 0, -1);
	std::vector <int> toc;
	auto rem = [&] (auto&& self, int node, int& mine, int& rest, int upp) -> void {
		if (fur[node] < upp && mine - sub[node] >= s[0].first) {
			stop[node] = true;
			toc.push_back(node);
			mine -= sub[node];
			rest += sub[node];
			return;
		}
		for (int x : h[node]) {
			self(self, x, mine, rest, upp);
		}
	};
	auto mak1 = [&] (auto&& self, int node, std::vector <bool>& ok) -> void {
		if (stop[node] || !s[0].first) {
			return;
		}
		ok[node] = false;
		ans[node] = s[0].second;
		s[0].first--;
		for (int x : h[node]) {
			self(self, x, ok);
		}
	};
	auto mak2 = [&] (auto&& self, int node, const std::vector <bool>& ok, std::vector <bool>& vs) -> void {
		if (!ok[node] || vs[node] || !s[1].first) {
			return;
		}
		vs[node] = true;
		ans[node] = s[1].second;
		s[1].first--;
		for (int x : g[node]) {
			self(self, x, ok, vs);
		}
	};
	auto dfs = [&] (auto&& self, int node) -> bool {
		bool all_less = true;
		for (int x : h[node]) {
			if (sub[x] >= s[0].first) {
				all_less = false;
				if (self(self, x)) {
					return true;
				}
			}
		}
		if (all_less) {
			int mine = sub[node];
			int rest = n - sub[node];
			rem(rem, node, mine, rest, dep[node]);
			if (rest >= s[1].first) {
				std::vector <bool> ok(n, true);
				std::vector <bool> vs(n, false);
				mak1(mak1, node, ok);
				assert(ans[0] == s[2].second);
				mak2(mak2, 0, ok, vs);
				return true;
			}
			for (int x : toc) {
				stop[x] = false;
			}
			toc.clear();
		}
		return false;
	};
	if (!dfs(dfs, 0)) {
		return std::vector <int> (n, 0);
	}
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36