제출 #614181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614181		AlperenT	Split the Attractions (IOI19_split)	C++17	40 / 100	543 ms	1048576 KiB

split

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

using namespace std;

const int N = 2e5 + 5;

vector<int> graph[N], 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(!que.empty() && curcnt < cnt){
		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(flag) return 0;

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

			for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 3;

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

			for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 2;

			flag = true;
			return 0;
		}
	}

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

			for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 3;

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

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

			flag = true;
			return 0;
		}
	}

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

			for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = 2;

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

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

			flag = true;
			return 0;
		}
	}

	return cnt;
}

vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q){
	n = n_, a = a_, b = b_, c = c_;
	int 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(0, -1);
	}
	else{ // Subtask 1
		graph[p[m - 1]].pop_back();
		graph[q[m - 1]].pop_back();

		dfs(0, -1);
	}

	return ans;
}

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