Submission #378512

#	Time	Username	Problem	Language	Result	Execution time	Memory
378512		autumn_eel	Split the Attractions (IOI19_split)	C++14	40 / 100	115 ms	20332 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct UnionFind{
	vector<int>par;
	UnionFind(int n){par=vector<int>(n);rep(i,n)par[i]=i;}
	int find(int x){
		return par[x]==x?x:par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x=find(x);y=find(y);
		par[y]=x;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
};

static vector<int>E[200000];
static int sz[200000],par[200000];
static vector<int>col;
static int cnt1=0,cnt2=0;

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

void dfs2(int v,int p,int c){
	if(cnt1==0)return;
	col[v]=c;
	cnt1--;
	for(int u:E[v]){
		if(u==p)continue;
		dfs2(u,v,c);
	}
}

void dfs3(int v,int p,int c){
	if(cnt2==0)return;
	col[v]=c;
	cnt2--;
	for(int u:E[v]){
		if(u==p||col[u]!=0)continue;
		dfs3(u,v,c);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m=p.size();
	col=vector<int>(n);

	UnionFind uf(n);
	rep(i,m){
		if(uf.same(p[i],q[i]))continue;
		E[p[i]].push_back(q[i]);
		E[q[i]].push_back(p[i]);
		uf.unite(p[i],q[i]);
	}

	vector<P>v{P(a,1),P(b,2),P(c,3)};
	sort(v.begin(),v.end());

	dfs(0,-1);

	rep(i,n){
		if(sz[i]>=v[0].first&&n-sz[i]>=v[1].first){
			cnt1=v[0].first;
			dfs2(i,par[i],v[0].second);
			cnt2=v[1].first;
			dfs3(0,-1,v[1].second);
			rep(i,n){
				if(col[i]==0)col[i]=v[2].second;
			}
			return col;
		}
		if(sz[i]>=v[1].first&&n-sz[i]>=v[0].first){
			cnt1=v[1].first;
			dfs2(i,par[i],v[1].second);
			cnt2=v[0].first;
			dfs3(0,-1,v[0].second);
			rep(i,n){
				if(col[i]==0)col[i]=v[2].second;
			}
			return col;
		}
	}
	return col;
}

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