Submission #1215396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215396		brinton	Split the Attractions (IOI19_split)	C++20	7 / 100	50 ms	17480 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<vector<int>> edges(N);
	vector<int> color(N,3);
	for(int i = 0;i < p.size();i++){
		edges[p[i]].push_back(q[i]);
		edges[q[i]].push_back(p[i]);
	}

	vector<int> vis(N,false);
	function<void(int,int,int)> dfs = [&](int cur,int par,int cidx){
		if(cidx < a) color[cur] = 1;
		else if(cidx < a+b) color[cur] = 2;
		vis[cur] = true;
		for(auto nxt:edges[cur]){
			if(nxt == par) continue;
			if(vis[nxt]) continue;
			dfs(nxt,cur,cidx+1);
		}
	};
	for(int i = 0;i < N;i++){
		if(edges[i].size() < 2){
			// start;
			dfs(i,-1,0);
			return color;
		}
	}

	dfs(0,-1,0);
	return color;
}

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