Submission #830486

#	Time	Username	Problem	Language	Result	Execution time	Memory
830486		pavement	Split the Attractions (IOI19_split)	C++17	22 / 100	454 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back

using ii = pair<int, int>;

int par[100005], sz[100005];
vector<int> tp, adj[100005];

int get_sz(int u, int e = -1) {
	sz[u] = 1;
	for (auto v : adj[u]) if (v != e) {
		par[v] = u;
		sz[u] += get_sz(v, u);
	}
	return sz[u];
}

void topo(int u, int e = -1) {
	for (auto v : adj[u]) if (v != e) {
		topo(v, u);
	}
	tp.pb(u);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = (int)p.size();
	for (int i = 0; i < m; i++) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	ii arr[3];
	arr[0] = mp(a, 1);
	arr[1] = mp(b, 2);
	arr[2] = mp(c, 3);
	sort(arr, arr + 3);
	get_sz(0);
	vector<int> out(n, 0);
	for (int i = 0; i < n; i++) {
		if (sz[i] >= arr[0].first && n - sz[i] >= arr[1].first) {
			tp.clear();
			topo(i, par[i]);
			for (int j = 0; j < (int)tp.size(); j++) {
				if (j < (int)tp.size() - arr[0].first) {
					out[tp[j]] = arr[2].second;
				} else {
					out[tp[j]] = arr[0].second;
				}
			}
			tp.clear();
			topo(par[i], i);
			for (int j = 0; j < (int)tp.size(); j++) {
				if (j < (int)tp.size() - arr[1].first) {
					out[tp[j]] = arr[2].second;
				} else {
					out[tp[j]] = arr[1].second;
				}
			}
			break;
		}
		if (n - sz[i] >= arr[0].first && sz[i] >= arr[1].first) {
			swap(arr[0], arr[1]);
			tp.clear();
			topo(i, par[i]);
			for (int j = 0; j < (int)tp.size(); j++) {
				if (j < (int)tp.size() - arr[0].first) {
					out[tp[j]] = arr[2].second;
				} else {
					out[tp[j]] = arr[0].second;
				}
			}
			tp.clear();
			topo(par[i], i);
			for (int j = 0; j < (int)tp.size(); j++) {
				if (j < (int)tp.size() - arr[1].first) {
					out[tp[j]] = arr[2].second;
				} else {
					out[tp[j]] = arr[1].second;
				}
			}
			break;
		}
	}
	return out;
}

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