Submission #538189

#	Time	Username	Problem	Language	Result	Execution time	Memory
538189		jamezzz	Split the Attractions (IOI19_split)	C++17	29 / 100	602 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

int rem,col,mark[3],sub[100005];
vector<int> res;
vector<int> AL[100005];

void dfs(int u,int p){
	sub[u]=1;
	for(int v:AL[u]){
		if(v==p)continue;
		dfs(v,u);
		sub[u]+=sub[v];
	}
}

void dfs2(int u,int p){
	if(rem==0)return;
	res[u]=col;
	--rem;
	for(int v:AL[u]){
		if(v==p)continue;
		dfs2(v,u);
	}
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
	vector<ii> x;
	x.pb({a,1});x.pb({b,2});x.pb({c,3});
	sort(all(x));
	for(int i=0;i<3;++i)mark[i]=x[i].se;
	
	res.resize(n);
	for(int i=0;i<n-1;++i){
		AL[p[i]].pb(q[i]);
		AL[q[i]].pb(p[i]);
	}
	dfs(0,-1);
	
	//for(ii pr:x)pf("(%d %d) ",pr.fi,pr.se);pf("\n");
	
	//for(int i=0;i<n;++i)pf("%d ",sub[i]);pf("\n");
	
	for(int u=0;u<n;++u){
		vector<ii> s;
		int p=-1;
		for(int v:AL[u]){
			if(sub[v]<sub[u])s.pb({sub[v],v});
			else p=v;
		}
		if(p!=-1)s.pb({n-sub[u],p});
		sort(all(s));
		//pf("%d: ",u);
		//for(ii pr:s)pf("(%d %d) ",pr.fi,pr.se);
		//pf("\n");
		int pos=lower_bound(all(s),ii(x[0].fi,-1))-s.begin();
		if(pos==sz(s))continue;
		if(n-1-s[pos].fi<x[1].fi)continue;
		int v=s[pos].se;
		//pf("%d %d\n",u,v);
		rem=x[0].fi;col=mark[0];dfs2(v,u);
		rem=x[1].fi;col=mark[1];dfs2(u,v);
		for(int j=0;j<n;++j)if(res[j]==0)res[j]=mark[2];
		return res;
	}
	
	return res;
}

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