Submission #1067884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067884		Gromp15	Split the Attractions (IOI19_split)	C++17	22 / 100	57 ms	11344 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;

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);
	}
	assert(0);
	return {};
}

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