Submission #428347

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

split

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

#define LL long long
#define F first
#define S second

using namespace std;

const int N = 2e5+10;
const LL INF = 1e9;

vector<int>adj[N],ans;
int n,m,sizes[N],vis[N],par[N],a,b,c,mn = INF;
pair<int,pair<int,int>>p1;
vector<pair<int,int>>vec;

void dfs(int i,int pre){

	sizes[i] = 1;par[i] = pre;
	for(auto x:adj[i])
		if(x!=pre)
			dfs(x,i),sizes[i] += sizes[x];

	if(sizes[i]>=a&&sizes[i]-a<mn)
		mn = sizes[i]-a,p1 = make_pair(i,make_pair(a,1));
	
	if(sizes[i]>=b&&sizes[i]-b<mn)
		mn = sizes[i]-b,p1 = make_pair(i,make_pair(b,2));

	if(sizes[i]>=c&&sizes[i]-c<mn)
		mn = sizes[i]-c,p1 = make_pair(i,make_pair(c,3));
}

void color(int i,int c,int &cnt){

	if(vis[i]||!cnt)
		return ;
	
	vis[i] = 1,ans[i] = c;
	cnt--;
	for(auto x:adj[i])
		color(x,c,cnt);
}

int cnt[4];

void f(){

	dfs(0,n);	
	vis[par[p1.F]] = 1;
	color(p1.F,p1.S.S,p1.S.F);
	vis[par[p1.F]] = 0;
	
	for(int i=2;i>=0;i--)
		if(p1.S.S!=vec[i].S){
			color(0,vec[i].S,vec[i].F);
			break;
		}

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

	int col = 0;
	for(int i=1;i<4;i++)
		if(!cnt[i])col = i;

	for(int i=0;i<n;i++)
		if(!ans[i])ans[i] = col,cnt[col]++;
	
	if(cnt[1]!=a||cnt[2]!=b||cnt[3]!=c)
		ans = vector<int>(n,0);	
}

vector<int> find_split(int n1, int a1, int b1, int c1, vector<int> p, vector<int> q) {

	n = n1;		m = p.size();	a = a1;		b  = b1;	c = c1;
	ans = vector<int>(n,0);
	
	vec.push_back({a,1});	vec.push_back({b,2});	vec.push_back({c,3});
	sort(vec.begin(),vec.end());

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

	f();
	if(!ans[0]){
		reverse(vec.begin(),vec.end());
		f();
	}

	return ans;
}

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