제출 #420899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420899		KoD	Split the Attractions (IOI19_split)	C++17	40 / 100	202 ms	31152 KiB

split

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

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

template <class F> struct RecLambda: private F {
	explicit RecLambda(F&& f): F(std::forward<F>(f)) {}
	template <class... Args> decltype(auto) operator () (Args&&... args) const {
		return F::operator()(*this, std::forward<Args>(args)...);
	}
};

struct Node {
	Vec<int> adjacent, children, tree;
	int parent, ord, low, subtree;
	Node() = default;
};

Vec<int> find_split(int n, int a, int b, int c, Vec<int> edge_p, Vec<int> edge_q) {
	std::array<int, 4> specified_size = {-1, a, b, c};
	std::array<int, 3> size_order = {1, 2, 3};
	std::sort(size_order.begin(), size_order.end(), [&](const int i, const int j) {
		return specified_size[i] < specified_size[j];
	});
	const auto [small, medium, big] = size_order;
	const auto small_sz = specified_size[small];
	const auto medium_sz = specified_size[medium];
	Vec<Node> node(n);
	for (int i = 0; i < (int) edge_p.size(); ++i) {
		const auto u = edge_p[i];
		const auto v = edge_q[i];
		node[u].adjacent.push_back(v);
		node[v].adjacent.push_back(u);
	}
	{
		int timer = 0;
		RecLambda([&](auto&& dfs, const int u, const int p) -> void {
			node[u].parent = p;
			node[u].ord = node[u].low = timer;
			timer += 1;
			node[u].subtree = 1;
			for (const auto v: node[u].adjacent) {
				if (v == p) {
					continue;
				}
				if (node[v].subtree == 0) {
					dfs(v, u);
					node[u].children.push_back(v);
					node[u].subtree += node[v].subtree;
					node[u].low = std::min(node[u].low, node[v].low);
				} else {
					node[u].low = std::min(node[u].low, node[v].ord);
				}
			}
			node[u].tree = node[u].children;
			if (p != -1) {
				node[u].tree.push_back(p);
			}
		})(0, -1);
	}
	Vec<int> ret(n);
	const auto write = RecLambda([&](auto&& dfs, const int u, const int p, const int w, int& c) -> void {
		if (c == 0 or ret[u] != 0) {
			return;
		}
		ret[u] = w;
		c -= 1;
		for (const auto v: node[u].tree) {
			if (v != p) {
				dfs(v, u, w, c);
			}
		}
	});
	for (int u = 0; u < n; ++u) {
		int p_sz = n - node[u].subtree;
		Vec<std::pair<int, int>> around;
		for (const auto v: node[u].children) {
			if (node[v].low < node[u].ord) {
				p_sz += node[v].subtree;
			} else {
				around.emplace_back(node[v].subtree, v);
			}
		}
		if (p_sz != 0) {
			assert(node[u].parent != -1);
			around.emplace_back(p_sz, node[u].parent);
		}
		bool less_a = true;
		const int len = (int) around.size();
		for (int i = 0; i < len; ++i) {
			const auto [s, v] = around[i];
			if (s >= small_sz) {
				less_a = false;
			}
			if (s >= small_sz and n - s >= medium_sz) {
				int tmp = small_sz;
				write(v, u, small, tmp);
				tmp = medium_sz;
				write(u, v, medium, tmp);
				goto finish;
			}
			if (s >= medium_sz and n - s >= small_sz) {
				int tmp = small_sz;
				write(u, v, small, tmp);
				tmp = medium_sz;
				write(v, u, medium, tmp);
				goto finish;
			}
		}
		if (less_a) {
			goto finish;
		}
	}
	RecLambda([&](auto&& dfs, const int u) -> void {
		int upper = n - node[u].subtree;
		if (upper >= a) {
			int tmp = small_sz;
			write(node[u].parent, u, small, tmp);
			tmp = medium_sz;
			write(u, node[u].parent, medium, tmp);
			return;
		}
		for (const auto v: node[u].children) {
			if (node[v].subtree >= medium_sz) {
				dfs(v);
				return;
			}
			if (node[v].subtree >= small_sz) {
				int tmp = small_sz;
				write(v, u, small, tmp);
				tmp = medium_sz;
				write(u, v, medium, tmp);
				return;
			}
		}
		Vec<int> seen;
		for (const auto v: node[u].children) {
			if (node[v].low < node[u].ord) {
				upper += node[v].subtree;
				seen.push_back(v);
			}
			if (upper >= small_sz) {
				break;
			}
		}
		if (upper >= medium_sz) {
			int tmp = medium_sz;
			write(node[u].parent, u, medium, tmp);
			for (const auto v: seen) {
				write(v, u, medium, tmp);
			}
			tmp = small_sz;
			write(u, node[u].parent, small, tmp);
		} else {
			int tmp = small_sz;
			write(node[u].parent, u, small, tmp);
			for (const auto v: seen) {
				write(v, u, small, tmp);
			}
			tmp = medium_sz;
			write(u, node[u].parent, medium, tmp);
		}
	})(0);
	finish:
	if (std::any_of(ret.begin(), ret.end(), [&](const int x) { return x != 0; })) {
		for (auto& x: ret) {
			if (x == 0) {
				x = big;
			}
		}
	}
	return ret;
}

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