Submission #817633

#	Time	Username	Problem	Language	Result	Execution time	Memory
817633		welleyth	Split the Attractions (IOI19_split)	C++17	18 / 100	65 ms	17692 KiB

split

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

using namespace std;

constexpr int N = (int)3e5;

vector<int> g[N];
int sz[N];
bool used[N];
int p[N];
mt19937 rnd(time(nullptr));

void dfs (int v){
	sz[v] = 1;
	used[v] = true;
	for(auto& to : g[v]){
		if(used[to]) continue;
		p[to] = v;
		dfs(to);
		sz[v] += sz[to];
	}
	return;
};

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
	bool group1 = true;
	int m = p.size();
	for(int i = 0; i < m; i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	for(int i = 0; i < n; i++){
		group1 &= (g[i].size() <= 2);
	}
	if(group1){
		int root = 0;
		for(int i = 0; i < n; i++){
			if(g[i].size() == 1)
				root = i;
		}
		queue<int> q;
		q.push(root);
		bool used[n];
		memset(used,0,sizeof used);
		vector<int> order;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			used[v] = true;
			order.push_back(v);
			for(auto& to : g[v]){
				if(!used[to]){
					used[to] = true;
					q.push(to);
				}
			}
		}
		vector<int> ans(n);
		for(int i = 0; i < a; i++){
			ans[order[i]] = 1;
		}
		for(int i = a; i < a+b; i++){
			ans[order[i]] = 2;
		}
		for(int i = a+b; i < a+b+c; i++){
			ans[order[i]] = 3;
		}
		return ans;
	}
	if(a == 1){
		bool used[n];
		memset(used,0,sizeof used);
		bool deleted = false;
		vector<int> ans(n);
		for(int i = 0; i < n; i++){
			if(g[i].size() == 1){
				deleted = true;
				used[i] = true;
				ans[i] = 1;
				break;
			}
		}
		if(!deleted){
			used[0] = true;
			ans[0] = 1;
			deleted = true;
		}
		int root = 0;
		if(used[root]) root++;
		queue<int> q;
		q.push(root);
		vector<int> order;
		while(!q.empty()){
			int v = q.front();
			q.pop();
			used[v] = true;
			order.push_back(v);
			for(auto& to : g[v]){
				if(!used[to]){
					used[to] = true;
					q.push(to);
				}
			}
		}
		for(int i = 0; i < b; i++){
			ans[order[i]] = 2;
		}
		for(int i = b; i < b+c; i++){
			ans[order[i]] = 3;
		}
		return ans;
	}
	if(m == n-1){
		int val[3] = {1,2,3};
		if(a > b){
			swap(a,b);
			swap(val[0],val[1]);
		}
		if(b > c){
			swap(b,c);
			swap(val[1],val[2]);
		}
		if(a > b){
			swap(a,b);
			swap(val[0],val[1]);
		}
		memset(used,0,sizeof used);
		memset(sz,0,sizeof sz);
		int root = 0;
		for(int i = 0; i < n; i++){
			if(g[i].size() > 1)
				root = i;
		}
		// root = rnd()%n;
		p[root] = -1;
		dfs(root);
		memset(used,0,sizeof used);
		vector<int> ans(n,0);
		for(int i = 0; i < n; i++){
			if(sz[i] >= a && n - sz[i] >= b){
				queue<int> q;
				q.push(i);
				used[i] = true;
				ans[i] = val[0];
				a--;
				while(!q.empty() && a > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[0];
					for(auto& to : g[v]){
						if(to == p[v]) continue;
						q.push(to);
						a--;
					}
				}
				q.push(p[i]);
				used[p[i]] = true;
				ans[p[i]] = val[1];
				b--;
				while(!q.empty() && b > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[1];
					for(auto& to : g[v]){
						if(used[to]) continue;
						q.push(to);
						b--;
					}
				}
				for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = val[2];
				return ans;
			}
			if(sz[i] >= b && n - sz[i] >= a){
				queue<int> q;
				q.push(i);
				used[i] = true;
				ans[i] = val[1];
				b--;
				while(!q.empty() && b > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[1];
					for(auto& to : g[v]){
						if(to == p[v]) continue;
						q.push(to);
						b--;
					}
				}
				q.push(p[i]);
				used[p[i]] = true;
				ans[p[i]] = val[0];
				a--;
				while(!q.empty() && a > 0){
					int v = q.front();
					q.pop();
					used[v] = true;
					ans[v] = val[0];
					for(auto& to : g[v]){
						if(used[to]) continue;
						q.push(to);
						a--;
					}
				}
				for(int i = 0; i < n; i++) if(ans[i] == 0) ans[i] = val[2];
				return ans;
			}
		}
		return ans;
	}
	return vector<int>(n,0);
}

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