Submission #830490

#	Time	Username	Problem	Language	Result	Execution time	Memory
830490		pavement	Split the Attractions (IOI19_split)	C++17	40 / 100	65 ms	17068 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);
}

namespace ufds {
	int lnk[100005], sz[100005];
	
	void init(int n) {
		iota(lnk, lnk + n, 0);
		fill(sz, sz + n, 1);
	}
	int find(int x) {
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) {
			return;
		}
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m = (int)p.size();
	ufds::init(n);
	for (int i = 0; i < m; i++) {
		if (ufds::find(p[i]) != ufds::find(q[i])) {
			adj[p[i]].pb(q[i]);
			adj[q[i]].pb(p[i]);
			ufds::unite(p[i], q[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: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36