Submission #418309

#	Time	Username	Problem	Language	Result	Execution time	Memory
418309		Aderfish	Split the Attractions (IOI19_split)	C++14	11 / 100	92 ms	12228 KiB

split

#include "split.h"

using namespace std;


vector<bool> visited;
vector<vector<int>> adj_list;
int left;

void dfs_sub_2(int i){
	if(visited[i]) return;
	visited[i] = true;
	left--;

	for(int j : adj_list[i]){
		if(left > 0){
			dfs_sub_2(j);
		}
	}
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res(n, 0);

	adj_list.assign(n, vector<int>());
	for(int i = 0; i < (int)p.size(); i++){
		int a = p[i];
		int b = q[i];
		adj_list[a].push_back(b);
		adj_list[b].push_back(a);
	}

	if(a == 1){
		visited.assign(n, false);
		left = b;
		dfs_sub_2(0);

		for(int i = 0; i < n; i++){
			if(visited[i]){
				res[i] = 2;
			}
			else res[i] = 3;
		}

		for(int i = 0; i < n; i++){
			if(res[i] == 3){
				res[i] = 1;
				break;
			}
		}
	}

	return res;
}

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