Submission #601015

#	Time	Username	Problem	Language	Result	Execution time	Memory
601015		Temmie	Split the Attractions (IOI19_split)	C++17	40 / 100	507 ms	1048576 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) {
	std::vector <std::pair <int, int>> s = { { _a, 1 }, { _b, 2 }, { _c, 3 } };
	std::sort(s.begin(), s.end());
	std::vector <std::vector <int>> g(n);
	int m = _u.size();
	std::vector <int> deg(n, 0);
	for (int i = 0; i < m; i++) {
		g[_u[i]].push_back(_v[i]);
		g[_v[i]].push_back(_u[i]);
		deg[_u[i]]++;
		deg[_v[i]]++;
	}
	bool al2 = true;
	for (int i = 0; i < n; i++) {
		al2 &= deg[i] <= 2;
	}
	if (al2 && n == m) {
		m--;
		g[_u[m]].pop_back();
		g[_v[m]].pop_back();
	}
	if (s[0].first == 1) {
		std::vector <int> ans(n, s[2].second);
		auto dfs = [&] (auto&& self, int node, int& left) -> void {
			if (!left || ans[node] != s[2].second) {
				return;
			}
			left--;
			ans[node] = s[1].second;
			for (int x : g[node]) {
				if (left) {
					self(self, x, left);
				}
			}
		};
		int tmp = s[1].first;
		dfs(dfs, 0, tmp);
		for (int i = 0; i < n; i++) {
			if (ans[i] == s[2].second) {
				ans[i] = s[0].second;
				break;
			}
		}
		return ans;
	}
	std::vector <int> sub(n), ans(n, s[2].second);
	auto fil = [&] (auto&& self, int node, int par, int col, int& left) -> void {
		if (!left) {
			return;
		}
		left--;
		ans[node] = col;
		for (int x : g[node]) {
			if (x == par) {
				continue;
			}
			self(self, x, node, col, left);
		}
	};
	auto dfs = [&] (auto&& self, int node, int par) -> bool {
		sub[node] = 1;
		for (int x : g[node]) {
			if (x == par) {
				continue;
			}
			if (self(self, x, node)) {
				return true;
			}
			sub[node] += sub[x];
		}
		for (int x : g[node]) {
			if (x == par) {
				continue;
			}
			if (sub[x] >= s[0].first && n - sub[x] >= s[1].first) {
				int tmp = s[0].first;
				fil(fil, x, node, s[0].second, tmp);
				tmp = s[1].first;
				fil(fil, node, x, s[1].second, tmp);
				return true;
			}
			if (sub[x] >= s[1].first && n - sub[x] >= s[0].first) {
				int tmp = s[1].first;
				fil(fil, x, node, s[1].second, tmp);
				tmp = s[0].first;
				fil(fil, node, x, s[0].second, tmp);
				return true;
			}
		}
		return false;
	};
	if (!dfs(dfs, 0, -1)) {
		return std::vector <int> (n, 0);
	}
	return ans;
}

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