Submission #614168

#	Time	Username	Problem	Language	Result	Execution time	Memory
614168		AlperenT	Split the Attractions (IOI19_split)	C++17	0 / 100	9 ms	9932 KiB

split

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

using namespace std;

const int N = 2e5 + 5;

vector<int> graph[N];

vector<int> ans;

int n, a, b, c;

void fill_ans(int v, int bad, int cnt, int typ){
	vector<bool> vis(n, false);

	int curcnt = 1;

	queue<int> que;

	que.push(v), vis[v] = true;

	while(curcnt < cnt){
		int v = que.front(); que.pop();

		for(auto e : graph[v]){
			if(!vis[e] && e != bad){
				vis[e] = true;
				que.push(e);

				curcnt++;

				if(curcnt == cnt) break;
			}
		}
	}

	for(int i = 0; i < n; i++) if(vis[i]) ans[i] = typ;
}

bool flag = false;

int dfs(int v, int p){
	if(flag) return 0;

	int cnt = 1;

	for(auto e : graph[v]){
		if(e != p) cnt += dfs(e, v);
	}

	if(cnt >= a){
		if(n - cnt >= b){
			fill_ans(v, p, a, 1);
			fill_ans(p, v, b, 2);

			flag = true;
			return 0;
		}
		else if(n - cnt >= c){
			fill_ans(v, p, a, 1);
			fill_ans(p, v, c, 3);

			flag = true;
			return 0;
		}
	}

	if(cnt >= b){
		if(n - cnt >= a){
			fill_ans(v, p, b, 2);
			fill_ans(p, v, a, 1);

			flag = true;
			return 0;
		}
		else if(n - cnt >= c){
			fill_ans(v, p, b, 2);
			fill_ans(p, v, c, 3);

			flag = true;
			return 0;
		}
	}

	if(cnt >= c){
		if(n - cnt >= a){
			fill_ans(v, p, c, 3);
			fill_ans(p, v, a, 1);

			flag = true;
			return 0;
		}
		else if(n - cnt >= b){
			fill_ans(v, p, c, 3);
			fill_ans(p, v, b, 2);

			flag = true;
			return 0;
		}
	}

	return cnt;
}

vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q){
	int n = n_, a = a_, b = b_, c = c_, m = p.size();

	ans.assign(n, 0);

	for(int i = 0; i < m; i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}

	if(a == 1){ // Subtask 2
		fill_ans(0, -1, b, 2);

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

		for(int i = 0; i < n; i++){
			if(ans[i] == 0){
				ans[i] = 3;
			}
		}
 	}
	else if(m == n - 1){ // Subtask 3
		dfs(1, 0);
	}
	else{ // Subtask 1
		for(int i = 0; i < a; i++) ans[i] = 1;
		for(int i = a; i < a + b; i++) ans[i] = 2;
		for(int i = a + b; i < a + b + c; i++) ans[i] = 3;
	}

	return ans;
}

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