Submission #288765

#	Time	Username	Problem	Language	Result	Execution time	Memory
288765		amiratou	Split the Attractions (IOI19_split)	C++14	22 / 100	671 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
const int MX = (int)(2e5+5);

ii options[3];
int N,s[MX],par[MX],ans[MX],nb,comp,nb2,color,m;
bitset<MX> vis;
vector<int> vec[MX];
void dfs(int node,int p){
	s[node]=1;
	par[node]=p;
	for(auto it:vec[node])
		if(it!=p)dfs(it,node),s[node]+=s[it];
}
void trav(int node,int p,int c){
	if(!nb)return;
	vis[node]=1;
	ans[node]=c;
	nb--;
	for(auto it:vec[node])
		if(it!=p)trav(it,node,c);
}
void explore(int node,int p){
	vis[node]=1;comp++;
	for(auto it:vec[node])
		if(!vis[it] && it!=p)
			explore(it,node);
}
void gimme(int node,int p,int c){
	if(!nb2)return;
	ans[node]=c;
	nb2--;
	for(auto it:vec[node])
		if(it!=p && !ans[it])gimme(it,node,c);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for (int i = 0; i < (int)(p.size()); ++i)
	{
		vec[p[i]].push_back(q[i]);
		vec[q[i]].push_back(p[i]);
	}
	vector<int> res(n,0);
	options[0]={a,min(b,c)},options[1]={b,min(a,c)},options[2]={c,min(a,b)};
	N=n,dfs(0,0);
	ii f={-1,-1};
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < 3; ++j)
			if(s[i]>=options[j].fi && (n-s[i])>=options[j].se){
				f={i,j};break;
			}
		if(f.fi!=-1)break;
	}
	//cerr<<f.fi<<" "<<f.se<<"\n";
	if(f.fi==-1)return res;
	else{
		if(!f.se){
			nb=a;
			if(min(b,c)==b)nb2=b,color=2,m=3;
			else nb2=c,color=3,m=2;
		}
		else if(f.se==1){
			nb=b;
			if(min(a,c)==a)nb2=a,color=1,m=3;
			else nb2=c,color=3,m=1;
		}
		else{ 
			nb=c;
			if(min(a,b)==a)nb2=a,color=1,m=2;
			else nb2=b,color=2,m=1;
		}
		cerr<<f.se+1<<" "<<color<<" "<<m<<"\n";
		trav(f.fi,par[f.fi],f.se+1);
		for (int i = 0; i < n; ++i)
			if(!vis[i]){
				comp=0;
				explore(i,i);
				//cerr<<i<<"\n";
				//cerr<<"comp : "<<comp<<" "<<options[f.se].se<<"\n";
				if(comp>=options[f.se].se){
					//assert(0);
					gimme(i,i,color);
					break;
				}
			}
		for (int i = 0; i < n; ++i)
		{
			if(ans[i])res[i]=ans[i];
			else res[i]=m;
		}
	}
	return res;
}

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