Submission #622106

#	Time	Username	Problem	Language	Result	Execution time	Memory
622106		cheissmart	Split the Attractions (IOI19_split)	C++14	40 / 100	133 ms	33528 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;

vi G[N];
vi T[N];

vi find_split(int n, int a, int b, int c, vi p, vi q) {
	int m = SZ(p);
	for(int i = 0; i < m; i++) {
		int u = p[i], v = q[i];
		G[u].PB(v);
		G[v].PB(u);
	}
	assert(a + b + c == n);
	pi aux[] = {pi(a, 1), pi(b, 2), pi(c, 3)};
	sort(aux, aux + 3);

	V<bool> vis(n);
	function<void(int)> dfs = [&] (int u) {
		vis[u] = true;
		for(int v:G[u]) if(!vis[v]) {
			T[u].PB(v);
			dfs(v);
		}
	};
	dfs(0);

	vi ans(n);
	bool flag = false;

	function<int(int)> dfs2 = [&] (int u) {
		int sz = 1;
		for(int v:T[u]) {
			int tt = dfs2(v);
			function<void(int, int&, int)> mark = [&] (int uu, int& need, int id) {
				if(!need) return;
				ans[uu] = id;
				need--;
				for(int vv:T[uu]) if(vv != v) {
					mark(vv, need, id);
				}
			};
			if(!flag && tt >= aux[0].F && n - tt >= aux[1].F) {
				ans = vi(n, aux[0].S ^ aux[1].S);
				mark(v, aux[0].F, aux[0].S);
				mark(0, aux[1].F, aux[1].S);
				assert(aux[0].F == 0);
				assert(aux[1].F == 0);
				flag = true;
			}
			if(!flag && tt >= aux[1].F && n - tt >= aux[0].F) {
				ans = vi(n, aux[0].S ^ aux[1].S);
				mark(v, aux[1].F, aux[1].S);
				mark(0, aux[0].F, aux[0].S);
				assert(aux[0].F == 0);
				assert(aux[1].F == 0);
				flag = true;
			}

			sz += tt;
		}
		return sz;
	};
	dfs2(0);

	return ans;
}

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