Submission #293557

#	Time	Username	Problem	Language	Result	Execution time	Memory
293557		DystoriaX	Split the Attractions (IOI19_split)	C++14	22 / 100	613 ms	1048580 KiB

split

#include "split.h"

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n;
int sz[100010];
vector<int> adj[100010];
vector<pair<int, int> > v;
bool found = false;
vector<int> res;

void Colour(int u, int p, int id){
	if(v[id].first == 0) return;

	res[u] = v[id].second;
	v[id].first--;

	for(auto &v : adj[u]){
		if(v == p) continue;

		Colour(v, u, id);
	}
}


void dfs(int u, int p) {
	sz[u] = 1;

	vector<pair<int, int> > sub;
	for(auto &v : adj[u]){
		if(v == p) continue;

		dfs(v, u);

		if(found) return;

		sz[u] += sz[v];

		sub.emplace_back(sz[v], v);
	}

	sub.emplace_back(n - sz[u], p);

	for(auto &k : sub){
		if(k.first >= v[0].first && n - k.first >= v[1].first){
			found = true;

			Colour(k.second, u, 0);
			Colour(u, k.second, 1);
			return;
		}
	}
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	n = _n;
	v.emplace_back(a, 1);
	v.emplace_back(b, 2);
	v.emplace_back(c, 3);

	sort(v.begin(), v.end());
	
	for(int i = 0; i < (int) p.size(); i++){
		adj[p[i]].emplace_back(q[i]);
		adj[q[i]].emplace_back(p[i]);
	}

	res.assign(n, 0);
	dfs(0, -1);

	if(found) for(auto &k : res) if(k == 0) k = v[2].second;

	return res;
}

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