Submission #256724

#	Time	Username	Problem	Language	Result	Execution time	Memory
256724		atoiz	Split the Attractions (IOI19_split)	C++14	100 / 100	241 ms	21376 KiB

split

#include "split.h"
#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <deque>

using namespace std;

vector<int> find_split(int n, int oA, int oB, int oC, vector<int> p, vector<int> q) {
	int m = (int) p.size();
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; ++i) {
		adj[p[i]].push_back(i);
		adj[q[i]].push_back(i);
	}

	vector<int> inTree(m, 0), vis(n, 0), par(n, -1), sz(n, 0);
	function<int(int)> findCentroid = [&](int u) -> int {
		vis[u] = true, sz[u] = 1;
		int cen = -1;
		for (int i : adj[u]) {
			int v = u ^ p[i] ^ q[i];
			if (vis[v]) continue;
			inTree[i] = true;
			int can = findCentroid(v);
			if (cen == -1) cen = can;
			sz[u] += sz[v];
		}
		if (cen == -1 && 2 * sz[u] >= n) cen = u;
		return cen;
	};
	int root = findCentroid(0);

	array<int, 3> arr = {oA, oB, oC};
	int a = *min_element(arr.begin(), arr.end()), c = *max_element(arr.begin(), arr.end()), b = n - a - c;

	vector<int> ans(n, 0);
	fill(vis.begin(), vis.end(), 0);
	vector<int> done(n, 0);
	done[root] = 1;
	for (int ir : adj[root]) if (inTree[ir]) {
		int u = root ^ p[ir] ^ q[ir];
		if (done[u]) continue;

		vector<int> vec;
		deque<int> dq = {u};
		while (!dq.empty()) {
			int v = dq.front();
			dq.pop_front();

			if (done[v]) continue;
			done[v] = true;
			vec.push_back(v);

			for (int i : adj[v]) {
				int w = v ^ p[i] ^ q[i];
				if (done[w]) continue;
				if (inTree[i]) {
					if (vis[w] < 2) {
						dq.push_front(w);
						vis[w] = 2;
					}
				} else {
					if (vis[w] < 1) {
						dq.push_back(w);
						vis[w] = 1;
					}
				}
			}
		}

		if ((int) vec.size() >= a) {
			vec.resize(a);
			for (auto v : vec) ans[v] = 1;
			break;
		}
	}

	if (count(ans.begin(), ans.end(), 1) != a) return ans;

	vis = ans;
	vector<int> vec = {root};
	vis[root] = true;
	for (int iv = 0; iv < (int) vec.size(); ++iv) {
		int u = vec[iv];
		for (int i : adj[u]) {
			int v = u ^ p[i] ^ q[i];
			if (vis[v]) continue;
			vis[v] = true;
			vec.push_back(v);
		}
	}
	assert((int) vec.size() >= b);
	vec.resize(b);
	for (int v : vec) ans[v] = 2;

	array<int, 3> idx = {0, 1, 2};
	sort(idx.begin(), idx.end(), [&](int i, int j) { return arr[i] < arr[j]; });
	for (int &x : ans) {
		if (x == 0) x = idx[2] + 1;
		else if (x == 1) x = idx[0] + 1;
		else x = idx[1] + 1;
	}

	return ans;
}

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