Submission #737964

#	Time	Username	Problem	Language	Result	Execution time	Memory
737964		bobthebuilder	Split the Attractions (IOI19_split)	C++17	100 / 100	148 ms	25444 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define MNTO(x,y) x=min(x,y)
const int maxn=1e5+5;
#define ll long long
vector<int> v[maxn];
bool vis[maxn];
vector<int> top;
int sz[maxn];
vector<int> val;
vector<int> cand;
vector<int> g[maxn];
int low[maxn],dep[maxn];
int cur=0;
int par[maxn];
int in[maxn],out[maxn];
void dfs(int u,int p){
	par[u]=p;
	low[u]=dep[u]=in[u]=(cur++);
	vis[u]=1;
	sz[u]=1;
	bool ok=1;
	for(int x:v[u]){
		if(x==p) continue;
		if(!vis[x]){
			dfs(x,u);
			g[u].pb(x);
			sz[u]+=sz[x];
			if(sz[x]>=val[0]){
				ok=0;
			}
			MNTO(low[u],low[x]);
		}
		else{
			MNTO(low[u],dep[x]);
		}
	}
	if(ok and sz[u]>=val[0]) cand.pb(u);
	out[u]=(cur-1);
}
bool sp[maxn];
void dfs2(int u){
	sp[u]=1;
	for(int x:g[u]){
		dfs2(x);
	}
}
//x inside a
bool ins(int x,int a){
	return (in[a]<=in[x] and out[x]<=out[a]);
}
vector<int> ans;
vector<int> asd={1,2,3};
void dfs3(int u){
	if(!val[1]) return;
	--val[1];
	ans[u]=asd[1];
	
	for(int x:v[u]){
		if(ans[x]) continue;
		if(sp[x] or !ins(x,cur)){
			dfs3(x);
		}
	}
}
void dfs4(int u){
	if(!val[0]) return;
	--val[0];
	ans[u]=asd[0];
	for(int x:g[u]){
		if(sp[x]) continue;
		dfs4(x);
	}
}
int col[maxn];
bool cmp(int a,int b){
	return val[a-1]<val[b-1];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	REP(i,n) ans.pb(0);
	REP(i,sz(p)){
		v[p[i]].pb(q[i]),v[q[i]].pb(p[i]);
	}
	val={a,b,c};
	sort(ALL(asd),cmp);
	sort(ALL(val));
	dfs(0,-1);
	for(int x:cand){
		if(!x) continue;
		cur=x;
		int tot=sz[x];
		bool swp=0;
		if(tot>=val[1]) swap(val[1],val[0]),swap(asd[0],asd[1]),swp=1;
		vector<int> oth;
		for(int z:g[x]){
			if(low[z]>=dep[x]){
				continue;
			}
			if(tot-sz[z]<val[0]) continue;
			oth.pb(z);
			tot-=sz[z];
		}
		if(n-tot<val[1]){
			if(swp) swap(val[1],val[0]),swap(asd[0],asd[1]);
			continue;
		}
		for(int z:oth){
			dfs2(z);
		}
		dfs3(par[x]);
		dfs4(x);
		REP(i,n) if(!ans[i]) ans[i]=asd[2];
		return ans;
	}
	return ans;
}

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