Submission #1215400

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

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> draw;
	{// a < b < c
	vector<pair<int,int>> need{{a,1},{b,2},{c,3}};
	sort(need.begin(),need.end());
	a = need[0].first,b = need[1].first,c = need[2].first;
	draw = {need[0].second,need[1].second,need[2].second};
	}
	vector<vector<int>> edges(N);
	vector<int> color(N,draw[2]);
	for(int i = 0;i < p.size();i++){
		edges[p[i]].push_back(q[i]);
		edges[q[i]].push_back(p[i]);
	}

	vector<vector<int>> child(N);
	vector<int> sz(N,1);
	function<void(int,int)> dfs = [&](int cur,int par){
		for(auto nxt:edges[cur]){
			if(nxt == par) continue;
			child[cur].push_back(nxt);
			dfs(nxt,cur);
		}
	};
	function<int(int)> set_sz = [&](int cur){
		for(auto nxt:child[cur]){
			sz[cur] += set_sz(nxt);
		}
		return sz[cur];
	};
	dfs(0,-1);
	set_sz(0);

	int root = -1;

	int s1,s2;
	function<void(int,int)> set_color1 = [&](int cur,int changeto){
		if(s1 > 0){
			color[cur] = changeto;
			s1--;
		}
		for(auto nxt:child[cur]){
			set_color1(nxt,changeto);
		}
	};
	function<void(int,int)> set_color2 = [&](int cur,int changeto){
		if(s2 > 0){
			color[cur] = changeto;
			s2--;
		}
		for(auto nxt:child[cur]){
			if(nxt == root) continue;
			set_color2(nxt,changeto);
		}
	};
	for(int i = 0;i < N;i++){
		if(sz[i] >= a && N-sz[i] >= b) {
			root = i;
			s1 = a,s2 = b;
			set_color1(i,draw[0]);
			set_color2(0,draw[1]);
			return color;
		}
		if(sz[i] >= b && N-sz[i] >= a) {
			s1 = b,s2 = a;
			set_color1(i,draw[1]);
			set_color2(0,draw[0]);
			root = i;
			return color;
		}
	}
	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