Submission #1068153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068153		Gromp15	Split the Attractions (IOI19_split)	C++17	40 / 100	116 ms	16508 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]);
	}
	if (m == n-1) {
		vector<int> sub(n), p(n, -1);
		auto dfs = [&](auto&& s, int v) -> void {
			sub[v] = 1;
			for (int u : adj[v]) if (u != p[v]) {
				p[u] = v;
				s(s, u);
				sub[v] += sub[u];
			}
		};
		dfs(dfs, 0);
		ar<int, 3> size{a, b, c};
		for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) {
			int other = 3 - i - j;
			for (int k = 0; k < n; k++) if (sub[k] >= size[i] && n - sub[k] >= size[j]) {
				vector<int> col(n, other+1);
				auto color = [&](auto&& s, int v, int P, int& left, int who) -> void {
					if (!left) return;
					col[v] = who;
					left--;
					for (int u : adj[v]) if (u != P) s(s, u, v, left, who);
				};
				color(color, k, p[k], size[i], i+1);
				color(color, p[k], k, size[j], j+1);
				return col;
			}
		}
		return vector<int>(n);
	}
	for (int t = 0; t < 100; t++) {
		for (int i = 0; i < n; i++) shuffle(all(adj[i]), rng);
		for (int r = 0; r < n; r++) {
			vector<int> sub(n), p(n, -1), dist(n, 1e9);
			vector<bool> vis(n);
			vector<vector<int>> adj2(n);
			queue<int> q;
			q.push(r);
			dist[r] = 0;
			while (q.size()) {
				int v = q.front(); q.pop();
				for (int u : adj[v]) if (ckmin(dist[u], dist[v] + 1)) {
					p[u] = v;
					adj2[u].emplace_back(v);
					adj2[v].emplace_back(u);
					q.push(u);
				}
			}
			auto dfs2 = [&](auto&& s, int v) -> void {
				sub[v] = 1;
				for (int u : adj2[v]) if (u != p[v]) {
					s(s, u);
					sub[v] += sub[u];
				}
			};
			dfs2(dfs2, r);
			ar<int, 3> size{a, b, c};
			for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) {
				int other = 3 - i - j;
				for (int k = 0; k < n; k++) if (sub[k] >= size[i] && n - sub[k] >= size[j]) {
					vector<int> col(n, other+1);
					auto color = [&](auto&& s, int v, int P, int& left, int who) -> void {
						if (!left) return;
						col[v] = who;
						left--;
						for (int u : adj2[v]) if (u != P) s(s, u, v, left, who);
					};
					color(color, k, p[k], size[i], i+1);
					color(color, p[k], k, size[j], j+1);
					return col;
				}
			}
		}
	}
	return vector<int>(n);
}

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