제출 #295702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295702		rqi	Split the Attractions (IOI19_split)	C++14	40 / 100	135 ms	19832 KiB

split

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

typedef vector<int> vi;

#define pb push_back
#define sz(x) (int)(x).size()

const int mx = 100005;

int n;
bool SUB1 = 1;
bool SUB2 = 1;
bool SUB3 = 1;
bool SUB4 = 1;
vi adj[mx];
vi res;

int sub[mx];
int par[mx];
vi children[mx];

void genSub(int node, int prv = -1){
	sub[node] = 1;
	for(auto u: adj[node]){
		if(u == prv) continue;
		children[node].pb(u);
		par[u] = node;
		genSub(u, node);
		sub[node]+=sub[u];
	}
}

int cnt;
void makeSub(int node, int num, int id){
	if(num != -1){
		cnt = num;
		makeSub(node, -1, id);
		return;
	}

	if(cnt == 0) return;
	res[node] = id;
	cnt--;
	for(auto u: children[node]) makeSub(u, -1, id);
}

void makenSub(int node, int num, int id, int prv = -1){
	//cout << node << " " << num << " " << id << " " << prv << "\n";
	if(num != -1){
		cnt = num;
		makenSub(node, -1, id, prv);
		return;
	}
	if(cnt == 0) return;
	res[node] = id;
	cnt--;
	if(node != 0 && par[node] != prv) makenSub(par[node], -1, id, node);
	for(auto u: children[node]) if(u != prv) makenSub(u, -1, id, node);
}

vi find_split(int _n, int a, int b, int c, vi p, vi q) {
	n = _n;
	res = vi(n, 0);
	for(int i = 0; i < sz(p); i++){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}

	
	
	for(int i = 0; i < n; i++){
		if(sz(adj[i]) > 2) SUB1 = 0;
	}
	if(a != 1) SUB2 = 0;
	if(sz(p) != n-1) SUB3 = 0;
	if(n > 2500 || sz(p) > 5000) SUB4 = 0;

	if(SUB1){
		int A = 0;
		int B = 0;
		int C = 0;
		int cur = 0;
		for(int i = 0; i < n; i++) if(sz(adj[i]) == 1) cur = i;

		int last = -1;

		while(true){
			if(A < a){
				res[cur] = 1;
				A++;
			}
			else if(B < b){
				res[cur] = 2;
				B++;
			}
			else if(C < c){
				res[cur] = 3;
				C++;
			}
			else break;

			if(adj[cur][0] == last){
				if(sz(adj[cur]) == 1) break;
				last = cur;
				cur = adj[cur][1];
			}
			else{
				last = cur;
				cur = adj[cur][0];
			}
		}

		return res;
	}

	if(SUB2){
		vi inComp(n, 0);
		queue<int> q;
		int B = 0;
		inComp[0] = 1;
		B++;
		q.push(0);
		while(sz(q)){
			int node = q.front();
			q.pop();
			for(auto u: adj[node]) if(inComp[u] == 0 && B < b){
				inComp[u] = 1;
				B++;
				q.push(u);
			}
			if(B == b) break;
		}	

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

		return res;
	}
	
	if(SUB3){
		genSub(0);

		for(int i = 0; i < n; i++){
			if(a <= sub[i] && min(b, c) <= n-sub[i]){
				//cout << i << "1\n";
				makeSub(i, a, 1);
				if(b <= c){
					makenSub(par[i], b, 2, i);
				}
				else{
					makenSub(par[i], c, 3, i);
				}
				break;
			}
			if(b <= sub[i] && min(a, c) <= n-sub[i]){
				//cout << i << "2\n";
				makeSub(i, b, 2);
				if(a <= c){
					makenSub(par[i], a, 1, i);
				}
				else{
					makenSub(par[i], c, 3, i);
				}
				break;
			}
			if(c <= sub[i] && min(a, b) <= n-sub[i]){
				//cout << i << "3\n";
				makeSub(i, c, 3);
				if(a <= b){
					makenSub(par[i], a, 1, i);
				}
				else{
					makenSub(par[i], b, 2, i);
				}
				break;
			}
		}
		vi full(4, 0);
		for(int i = 0; i < n; i++) full[res[i]] = 1;
		if(full[1] == 0 && full[2] == 0 && full[3] == 0){
			return res;
		}
		for(int i = 1; i <= 3; i++) if(full[i] == 0){
			for(int j = 0; j < n; j++){
				if(res[j] == 0) res[j] = i;
			}
		}
		return res;
	}

	return res;
}

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