Submission #297734

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

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
const int MX = (int)(1e5+5);

vector<int> vec[MX],res;
int s[MX],A,B,C,c_a,c_b,c_c,cnt,N;
bool g;
void dfs(int node,int p){
	s[node]=1;
	for(auto it:vec[node])
		if(it!=p)dfs(it,node),s[node]+=s[it];
}
bool comp(int a,int b){
	if(s[a]!=s[b])return s[a]>s[b];
	return a<b;
}
int solve(int node){
	//cerr<<node<<" , ";
	//cerr<<sz(vec[node])<<"\n";
	sort(vec[node].begin(),vec[node].end(),comp);
	if(A==1 && sz(vec[node])>=1 && s[vec[node][0]]>=B)return node;
	if(sz(vec[node])==1){s[node]-=s[vec[node][0]];s[vec[node][0]]=N;return solve(vec[node][0]);}
	else if(sz(vec[node])>=2){
		if(s[vec[node][0]]>=B && (s[vec[node][1]]+1)>=A)return node;
		else if(s[vec[node][0]]>=A && (s[vec[node][1]]+1)>=B){g=1;return node;}
		else if((s[vec[node][0]]<B && (s[vec[node][1]]+1)<A) && (s[vec[node][0]]<A && (s[vec[node][1]]+1)<B))return -1;
		s[node]-=s[vec[node][0]];
		s[vec[node][0]]=N;
		return solve(vec[node][0]);
	}
	return -1;	
}
void gimme(int node,int p,int o=0){
	if(!cnt)return;
	cnt--;
	//cerr<<node<<" "<<o<<"\n";
	if(!o)res[node]=c_a;
	else res[node]=c_b;
	for(auto it:vec[node])
		if(it!=p)gimme(it,node,o);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n;
	res.resize(n);
	fill(res.begin(),res.end(),0);
	for (int i = 0; i < n-1; ++i)
	{
		vec[p[i]].push_back(q[i]);
		vec[q[i]].push_back(p[i]);
	}
	dfs(0,0);
	c_a=1,c_b=2,c_c=3;
	if(a>b)swap(a,b),swap(c_a,c_b);
	if(a>c)swap(a,c),swap(c_a,c_c);
	if(b>c)swap(b,c),swap(c_b,c_c);
	///*cerr<<a<<" "<<b<<" "<<c<<"\n";
	//cerr<<c_a<<" "<<c_b<<" "<<c_c<<"\n";*/
	A=a,B=b,C=c;
	int idx=solve(0);
	if(idx==-1)
		return res;
	//cerr<<idx<<"\n";
	if(g){
		res[idx]=c_b;
		if(B!=1)cnt=B-1,gimme(vec[idx][1],idx,1);
		cnt=A,gimme(vec[idx][0],idx);
	}
	else{
		res[idx]=c_a;
		if(A!=1)cnt=A-1,gimme(vec[idx][1],idx);
		cnt=B,gimme(vec[idx][0],idx,1);
	}
	for (int i = 0; i < n; ++i)
		if(!res[i])res[i]=c_c;
	return res;
}

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