Submission #293553

#	Time	Username	Problem	Language	Result	Execution time	Memory
293553		DystoriaX	Split the Attractions (IOI19_split)	C++14	0 / 100	623 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);

	sort(sub.begin(), sub.end());

	int id = 0, sk[2];
	bool used = false;

	for(auto &k : sub){
		if(k.first >= v[id].first || (id == 0 && k.first + 1 >= v[id].first)){
			if(k.first >= v[id].first);
			else used = true;
			sk[id++] = k.second;
		}
	}

	if(id == 2) {
		found = true;

		Colour(sk[0], u, 0);
		Colour(sk[1], u, 1);

		if(used) res[u] = v[0].second;
	} else {
		id = 0;
		used = false;

		for(auto &k : sub){
			if(k.first >= v[id].first || (id == 1 && k.first + 1 >= v[id].first)){
				if(k.first >= v[id].first);
				else used = true;
				sk[id++] = k.second;
			}
		}

		if(id == 2) {
			found = true;

			Colour(sk[0], u, 0);
			Colour(sk[1], u, 1);

			if(used) res[u] = v[1].second;
		}
	}
}

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: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36