Submission #1210509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210509		bangan	Split the Attractions (IOI19_split)	C++20	0 / 100	570 ms	1114112 KiB

split

#include "split.h"
using namespace std;

#define X first 
#define Y second
#define pair pair<int, int>

#define pb push_back
#define all(a) a.begin(), a.end()

const int N = 2e5 + 4;

vector<int> adj[N];
int sub[N];
int fa[N];
bool dead[N];
vector<int> ans;
vector<pair> ord;

void prep(int v) {	
	for (int u : adj[v]) if (u != fa[v]) {
		fa[u] = v;
		prep(u);
		sub[v] += sub[u];
	}
}

void kill(int v, int id) {
	dead[v]=1;
	ans[v] = id;
	for (int u : adj[v]) if (u != fa[v]) kill(u, id);
}

void assign(int v, int cnt, int id) {
	if (cnt>0) ans[v] = id, cnt--;
	for (int u : adj[v]) if (u != fa[v] && !dead[u]) assign(u, cnt, id);
}

bool work(int n) {
	ans.resize(n);
	fill(all(ans), 0);
	fill(dead, dead+n, false);
	int v=0;
	for (int i=0; i<n; i++) if (sub[i]>=ord.back().X && sub[i]<sub[v]) v=i;
	kill(v, ord.back().Y);
	ord.pop_back();
	if (!dead[0]) assign(0, ord.back().X, ord.back().Y);
	if (count(all(ans), ord.back().Y) != ord.back().X) return 0;
	ord.pop_back();
	for (int i=0; i<n; i++) if (!ans[i]) ans[i] = ord.back().Y;
	return 1;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for (int i=0; i<p.size(); i++) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	prep(0);
	ord = {{a,1}, {b,2}, {c,3}};
	sort(all(ord), [&](auto lhs, auto rhs) {
		return lhs.X > rhs.X;
	});
	if (work(n)) return ans;
	ord = {{a,1}, {b,2}, {c,3}};
	sort(all(ord), [&](auto lhs, auto rhs) {
		return lhs.X > rhs.X;
	});
	swap(ord[1], ord[2]);
	if (work(n)) return ans;
	return vector<int>(n,0);
}

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