Submission #1047688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047688		MercubytheFirst	Split the Attractions (IOI19_split)	C++14	11 / 100	53 ms	10072 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;

vector<signed> find_split(signed n, signed a, signed b, signed c, vector<signed> p, vector<signed> q) {
	vector<signed> res(n);
	vector<vector<int> > g(n);
	int m = p.size();
	vector<bool> vis(n);
	for(int i = 0; i < m; ++i) {
		const int u = p[i];
		const int v = q[i];
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bool ok = false;
	for(int i = 0; i < n; ++i) {
		if(g[i].size() == 1u) {
			ok = true;
			res[i] = 1;
			vis[i] = true;
			break;
		}
	}
	if(!ok) {
		res[0] = 1;
		vis[0] = true;
	}
	int startv = 0;
	while(res[startv]) {
		startv++;
	}
	int quota = b;
	
	auto b_dfs = [&](auto&& dfs, int u) -> void
	{
		assert(quota >= 0);
		if(quota == 0) {
			return;
		}
		assert(!vis[u] and !res[u]);
		vis[u] = true;
		res[u] = 2;
		quota--;
		for(int to : g[u]) {
			if(!vis[to]) {
				dfs(dfs, to);
				assert(quota >= 0);
				if(quota == 0) {
					return;
				}
			}
		}
	};

	b_dfs(b_dfs, startv);
	for(int i = 0; i < n; ++i) {
		if(!res[i]) {
			res[i] = 3;
		}
	}
	return res;
}


/*
6 5
1 3 2
0 1      
0 2
0 3
0 4
0 5
*/

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