Submission #809165

#	Time	Username	Problem	Language	Result	Execution time	Memory
809165		Username4132	Split the Attractions (IOI19_split)	C++14	18 / 100	104 ms	34140 KiB

split

#include "split.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second

const int MAXN = 100010;
int n, top, sito, A, B, C, tm, tin[MAXN], low[MAXN], si[MAXN];
bool vis[MAXN], done;
vector<int> g[MAXN], tr[MAXN], ch;

int target, obt=1, roo2;
int ta2, ob2;
vector<int> res[3];
bool marked[MAXN], used[MAXN];

void dfs1(int v, int p){
	si[v]=1;
	vis[v]=true;
	tin[v]=tm++;
	int forced=1;
	bool atm=true;
	vector<int> fset, rest;
	for(int to:g[v]){
		if(to==p) continue;
		if(vis[to]){
			low[v]=min(low[v], tin[to]);
		}
		else{
			tr[v].PB(to);
			dfs1(to, v);
			si[v]+=si[to];
			atm&=(si[to]<A);
			low[v]=min(low[v], low[to]);
			if(low[to]>=tin[v]){
				forced+=si[to];
				fset.PB(to);
			}
			else rest.PB(to);
		}
	}
	if(atm && (si[v]>=A) && !done){
		done = true;
		roo2=p;
		if(forced>n-A) top=-1;
		else{
			top=v;
			sito=forced;
			for(int el:fset) ch.PB(el);
			while(sito<A){
				ch.PB(rest.back());
				sito+=si[rest.back()];
				rest.pop_back();
			}
		}
	}
}

void dfs2(int v){
	if(obt<target){
		used[v]=marked[v]=true;
		res[0].PB(v);
		++obt;
	}
	for(int to:tr[v]) dfs2(to);
}

void dfs3(int v){
	vis[v]=true;
	if(ob2<ta2){
		++ob2;
		used[v]=true;
		res[1].PB(v);
	}
	for(int to:g[v]) if(!vis[to] && !marked[to]) dfs3(to);
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n=N;
	vector<pii> col = {{a, 0}, {b, 1}, {c, 2}};
	sort(col.begin(), col.end());
	A = col[0].F, B = col[1].F, C = col[2].F;
	forn(i, p.size()){
		g[p[i]].PB(q[i]);
		g[q[i]].PB(p[i]);
	}

	dfs1(0, 0);

	if(top==-1){
		vector<int> ret(n, 0);
		return ret;
	}

	if(sito>=B) target=B, ta2=A;
	else target=A, ta2=B;

	for(int el:ch) dfs2(el);
	marked[top]=used[top]=true;
	res[0].PB(top);

	forn(i, n) vis[i]=false;
	dfs3(roo2);

	if((int)res[0].size()==B) swap(res[0], res[1]);
	forn(i, n) if(!used[i]) res[2].PB(i);
	vector<int> ret(n);
	forn(i, 3) for(int el:res[i]) ret[el]=col[i].S + 1;

	int car[3];
	car[0]=car[1]=car[2]=0;
	for(int el:ret) car[el-1]++;
	assert(car[0]==a && car[1]==b && car[2]==c);
	return ret;
}

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