Submission #1068260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068260		Gromp15	Split the Attractions (IOI19_split)	C++17	0 / 100	2066 ms	600 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]), dist(n, 1e9);
		queue<int> q;
		dist[comp[0]] = 0;
		q.push(comp[0]);
		int got = 0;
		while (q.size()) {
			int v = q.front(); q.pop();
			if (got > A) break;
			ans[v] = c1, got++;
			for (int u : adj[v]) if (in[u] && ckmin(dist[u], dist[v] + 1)) {
				q.push(u);
			}
		}
		if (got != A) while (1) {}
		int got2 = 0;
		for (int x : comp) { 
			if (ans[x] == ord[2]) { 
				ans[x] = c2;
				if (++got2 == B) break;
			}
		}
		if (got2 != B) while (1) {}
		return ans;
	}
	for (int i = 0; i < n; i++) if (ap[i]) {
		vector<vector<int>> nodes;
		vector<bool> vis(n);
		int cur = 0;
		auto dfs = [&](auto&& s, int v) -> void {
			nodes.back().push_back(v);
			cur++, vis[v] = 1;
			for (int u : adj[v]) if (!vis[u] && u != i) s(s, u);
		};
		int mx = 0;
		for (int j : adj[i]) if (!vis[j]) {
			cur = 0;
			nodes.push_back({});
			dfs(dfs, j);
			ckmax(mx, cur);
		}
		for (const auto& comp : nodes) if (sz(comp) >= A && n - sz(comp) >= 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;
		}
	}
	return vector<int>(n);
}

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