Submission #295803

#	Time	Username	Problem	Language	Result	Execution time	Memory
295803		ChrisT	Split the Attractions (IOI19_split)	C++17	7 / 100	137 ms	14456 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MN = 1e5+5;
vector<int> adj[MN];
int sz[MN], p[MN]; bool vis[MN];
int dfs (int cur) {
	vis[cur] = 1;
	for (int i : adj[cur]) if (!vis[i]) {
		p[i] = cur; 
		sz[cur] += dfs(i);
	}
	return ++sz[cur];
}
int getcent (int cur, int tot) {
	for (int i : adj[cur]) if (p[i] == cur && sz[i] > (tot >> 1))
		return getcent(i,tot);
	return cur;
}
vector<int> find_split (int n, int a, int b, int c, vector<int> P, vector<int> Q) {
	vector<pair<int,int>> vv = {{a,1},{b,2},{c,3}};
	sort(vv.begin(),vv.end());
	vector<int> ret(n,vv[2].second);
	a = vv[0].first; b = vv[1].first; c = vv[2].first;
	for (int i = 0; i < (int)P.size(); i++) {
		adj[++P[i]].push_back(++Q[i]);
		adj[Q[i]].push_back(P[i]);
	}
	auto fillB = [&] (int st, int go, int put) {
		queue<int> q; q.push(st);
		while (go--) {
			int cur = q.front(); q.pop(); ret[cur-1] = put;
			for (int i : adj[cur]) if (ret[i-1] == vv[2].second) q.push(i);
		}
	};
	int cent = getcent(1,dfs(1));
	for (int i : adj[cent]) if (p[i] == cent && sz[i] >= a) {
		queue<int> q; q.push(i);
		while (a--) {
			int cur = q.front(); q.pop(); ret[cur-1] = vv[0].second;
			for (int j : adj[cur]) if (p[j] == cur) q.push(j);
		}
		fillB(cent,b,vv[1].second);
		return ret;
	}
	vector<vector<int>> ree; vector<int> cnt,in;
	for (int i : adj[cent]) if (p[i] == cent) {
		in.push_back((int)ree.size()); ree.push_back({i}); cnt.push_back(sz[i]);
	}
	for (int i = 0; i < (int)P.size(); i++) if (p[P[i]] != Q[i] && p[Q[i]] != P[i] && in[P[i]] != in[Q[i]]) {
		int u = in[P[i]], v = in[Q[i]];
		if (cnt[u] > cnt[v]) swap(u,v);
		cnt[v] += cnt[u];
		for (int j : ree[u]) {in[j] = v; ree[v].push_back(j);}
	}
	for (int i = 0; i < (int)ree.size(); i++) if (cnt[i] >= a) {
		while (cnt[i] - sz[ree[i].back()] >= a) {
			ree[i].pop_back(); cnt[i] -= sz[ree[i].back()];
		} 
		for (int j : ree[i]) {
			queue<int> q; q.push(j);
			while (a && !q.empty()) {
				int cur = q.front(); q.pop(); --a; ret[cur-1] = vv[0].second;
				for (int k : adj[cur]) if (p[k] == cur) q.push(k);
			}
		}
		fillB(cent,b,vv[1].second);
		return ret;
	}
	fill(ret.begin(),ret.end(),0);
	return ret;
}

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