Submission #296677

#	Time	Username	Problem	Language	Result	Execution time	Memory
296677		rqi	Split the Attractions (IOI19_split)	C++14	0 / 100	1567 ms	1048580 KiB

split

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

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) begin(x), end(x)

const int mx = 100005;

int n, a, b, c;
vi L;
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);
}

bool visited[mx];
vi comp;

void getComp(int node){
	if(visited[node]) return;
	visited[node] = 1;
	comp.pb(node);
	for(auto u: adj[node]){
		getComp(u);
	}
}

int tcount;

void assign2(int node){
	if(tcount >= L[1]) return;
	if(res[node] != 0) return;
	res[node] = 2;
	tcount++;
	for(auto u: adj[node]){
		assign2(u);
	}
}

void adjustRes(){
	vi to(4, 0);
	vpi cnt;
	cnt.pb(mp(a, 1)); cnt.pb(mp(b, 2)); cnt.pb(mp(c, 3));
	sort(all(cnt));
	for(int i = 0; i < 3; i++) to[i+1] = cnt[i].s;

	for(auto &u: res) u = to[u];
}

void search(int node){
	//cout << "node: " << node << "\n";
	visited[node] = 1;
	vi good;

	for(auto u: adj[node]){
		if(visited[u]) continue;
		getComp(u);
		// cout << "u: " << u << "\n";
		// for(auto u: comp) cout << u << " ";
		// cout << "\n";

		if(sz(comp) < L[0]){

		}
		else{
			//cout << "SOLFOUND\n";
			if(n-sz(comp) >= L[1]){
				//solution found!
				for(int i = 0; i < n; i++){
					res[i] = 0;
				}
				int ocount = 0;
				for(auto u: comp){
					if(ocount < L[0]){
						ocount++;
						res[u] = 1;
					}
					else res[u] = -1;
				}

				for(auto u: res) if(u == 0){
					tcount = 0;
					assign2(u);
					break;
				}

				for(int i = 0; i < sz(res); i++){
					if(res[i] != 1 && res[i] != 2) res[i] = 3;
				}

				return;
			}
			good = comp;
		}
	}

	for(auto u: good){
		visited[u] = 0;
	}

	for(auto u: adj[node]){
		if(visited[u]) continue;
		search(u);
		return;
	}
}



vi find_split(int _n, int _a, int _b, int _c, vi p, vi q) {
	n = _n;
	a = _a;
	b = _b;
	c = _c;
	L.pb(a);
	L.pb(b);
	L.pb(c);
	sort(all(L));

	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;
	// }

	if(SUB4){
		search(0);

		int onecount = 0;
		for(auto u: res) if(u == 1) onecount++;
		if(onecount != L[0]){
			return vi(n, 0);
		}
		adjustRes();

		return res;
	}

	return res;
}

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