Submission #1068363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068363		Gromp15	Split the Attractions (IOI19_split)	C++17	18 / 100	2039 ms	27004 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<vector<int>> adj(n);
	int m = sz(p);
	for (int i = 0; i < m; i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	vector<int> tin(n), low(n), stk;
	vector<bool> ap(n);
	vector<vector<int>> comps;
	int timer = 0;
	auto dfs = [&](auto&& s, int v, int p) -> void {
		tin[v] = low[v] = ++timer;
		stk.emplace_back(v);
		for (int u : adj[v]) if (u != p) {
			if (!tin[u]) {
				s(s, u, v);
				ckmin(low[v], low[u]);
				if (low[u] >= tin[v]) {
					ap[v] = 1;
					comps.push_back({v});
					for (int x = -1; x != u; ) {
						x = stk.back();
						stk.pop_back();
						comps.back().push_back(x);
					}
				}
			}
			else ckmin(low[v], tin[u]);
		}
	};
	dfs(dfs, 0, -1);
	ar<int, 3> size{a, b, c}, ord{1, 2, 3};
	sort(all(ord), [&](int x, int y) { return size[x-1] < size[y-1]; });
	int c1 = ord[0], c2 = ord[1], A = size[ord[0]-1], B = size[ord[1]-1];
	for (const auto& comp : comps) if (sz(comp) >= A + B) {
		vector<bool> in(n);
		for (int x : comp) in[x] = 1;
		vector<int> ans(n, ord[2]);
		vector<int> deg(n);
		for (int x : comp) for (int u : adj[x]) if (in[u]) deg[u]++;
		set<ar<int, 2>> q;
		int who = -1;
		for (int x : comp) if (!~who || deg[x] < deg[who]) who = x;
		q.insert({deg[who], who});
		int got = 0;
		while (q.size()) {
			auto [_deg, v] = *q.begin();
			q.erase(q.begin());
			ans[v] = c1;
			if (++got == A) break;
			for (int u : adj[v]) if (in[u] && ans[u] == ord[2]) {
				if (q.count({deg[u], u})) q.erase({deg[u], u});
				deg[u]--;
				q.insert({deg[u], u});
			}
		}
		if (got != A) while (1) {}
		assert(got == A);
		auto dfs = [&](auto&& s, int v, int col, int target, int& got) -> void {
			if (got >= target) return;
			got++, ans[v] = col;
			for (int u : adj[v]) {
				deg[u]--;
			}
			while (got < target) {
				int who = -1;
				for (int u : adj[v]) if (in[u] && ans[u] == ord[2] && (!~who || deg[u] < deg[who])) who = u;
				if (~who) s(s, who, col, target, got);
				else break;
			}
		};
		int g = 0;
		for (int x : comp) if (ans[x] == ord[2]) {
			dfs(dfs, x, c2, B, g);
			assert(g == B);
			break;
		}
		return ans;
	}
	ap[0] = 1;
	for (int t = 0; t < 2; t++) {
		for (int i = 0; i < n; i++) if (ap[i]) {
			vector<vector<int>> nodes;
			vector<bool> vis(n);
			auto dfs = [&](auto&& s, int v) -> void {
				nodes.back().push_back(v);
				vis[v] = 1;
				for (int u : adj[v]) if (!vis[u] && u != i) s(s, u);
			};
			for (int j : adj[i]) if (!vis[j]) {
				nodes.push_back({});
				dfs(dfs, j);
			}
			for (const auto& comp : nodes) if (sz(comp) >= A && n - sz(comp) - 1 >= B) {
				vector<int> ans(n, ord[2]);
				int got2 = 0;
				auto dfs3 = [&](auto&& s, int v) -> void {
					if (got2 >= A) return;
					got2++, ans[v] = c1;
					for (int u : adj[v]) if (u != i && ans[u] == ord[2]) s(s, u);
				};
				dfs3(dfs3, comp[0]);
				int got = 0;
				auto dfs2 = [&](auto&& s, int v) -> void {
					if (got >= B) return;
					got++, ans[v] = c2;
					for (int u : adj[v]) if (ans[u] == ord[2]) s(s, u);
				};
				dfs2(dfs2, i);
				assert(got2 == A);
				assert(got == B);
				return ans;
			}
		}
		swap(c1, c2);
		swap(A, B);
	}
	return vector<int>(n);
}

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