Submission #297752

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

split

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

vector<ii> vec[MX];
vector<int> res;
int s[MX],A,B,C,c_a,c_b,c_c,cnt,N;
bool g;
int solve(int node,int p){
	int ans=1;
	for(auto it:vec[node])
		if(it.fi!=p){
			if(it.se==-1)it.se=solve(it.fi,node);
			ans+=it.se;
		}
	return ans;	
}
void gimme(int node,int p,int o=0){
	if(!cnt)return;
	cnt--;
	if(!o)res[node]=c_a;
	else res[node]=c_b;
	for(auto it:vec[node])
		if(it.fi!=p)gimme(it.fi,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],-1});
		vec[q[i]].push_back({p[i],-1});
	}
	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);
	A=a,B=b,C=c;
	for (int i = 0; i < n; ++i)
	{
		vector<ii> h;
		for(auto &it:vec[i]){
			if(it.se==-1)it.se=solve(it.fi,i);
			h.push_back({it.se,it.fi});
		}	
		sort(h.begin(),h.end(),greater<ii>());
		if(A==1 && h[0].fi>=B){
			cnt=B,gimme(h[0].se,i,1);
			res[i]=c_a;
			g=1;
			break;
		}
		if(h[0].fi>=B && (h[1].fi+1)>=A){
			cnt=B,gimme(h[0].se,i,1);
			res[i]=c_a;
			if(A!=1)cnt=A-1,gimme(h[1].se,i);
			g=1;
			break;
		}
		else if(h[0].fi>=A && (h[1].fi+1)>=B){
			cnt=A,gimme(h[0].se,i);
			res[i]=c_b;
			if(B!=1)cnt=B-1,gimme(h[1].se,i,1);
			g=1;
			break;
		}
	}	
	if(!g)return res;
	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