Submission #374440

#	Time	Username	Problem	Language	Result	Execution time	Memory
374440		pit4h	Split the Attractions (IOI19_split)	C++14	100 / 100	216 ms	32268 KiB

split

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

const int MAXN = 2e5+1;
vector<int> g[MAXN];
vector<int> res;
int found;
int n, d[MAXN], subt[MAXN], low[MAXN];
bool vis[MAXN];
int A, B;

void get(int x, int val) {
	res[x] = val;
	for(int i: g[x]) {
		if(d[i] == d[x]+1) {
			get(i, val);
		}
	}
}

void dfs(int x) {
	low[x] = d[x], vis[x] = 1, subt[x] = 1;
	bool candidate = 1;
	int over = 0;
	for(int i: g[x]) {
		if(!vis[i]) {
			d[i] = d[x]+1;
			dfs(i);
			subt[x] += subt[i], low[x] = min(low[x], low[i]);
			if(subt[i] >= A) {
				candidate = 0;
			}
			if(low[i] < d[x]) {
				over += subt[i];
			}
		}
		else {
			low[x] = min(low[x], d[i]); 
		}
	}
	if(!found && candidate && subt[x] >= A) {
		if(n-subt[x] + over >= B) {
			found = 1;
			res.clear(), res.resize(n, 2);
			res[x] = 1;
			int add = B - (n-subt[x]); 			
			for(int i: g[x]) {
				if(add > 0 && d[i] == d[x]+1 && low[i] < d[x]) {
					add -= subt[i];
				}
				else if(d[i] == d[x]+1) {
					get(i, 1);	
				}
			}
		}
		else if(n-subt[x] + over >= A) {
			found = 1;
			res.clear(), res.resize(n, 1);
			res[x] = 2;
			int add = A - (n-subt[x]);
			for(int i: g[x]) {
				if(add > 0 && d[i] == d[x]+1 && low[i] < d[x]) {
					add -= subt[i];
				}
				else if(d[i] == d[x]+1) {
					get(i, 2);
				}
			}
		}
	}
}

vector<int> tree[MAXN];
int deg[MAXN];
bool vist[MAXN];
void dfst(int x) {
	vist[x] = 1;
	for(int i: g[x]) {
		if(!vist[i] && res[x]==res[i]) {
			tree[i].push_back(x), tree[x].push_back(i);
			deg[i]++, deg[x]++;

			dfst(i);
		}
	}
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	n = _n;
	int m = p.size();
	A = min({a, b, c});
	B = a+b+c - min({a, b, c}) - max({a, b, c});

	for(int i=0; i<m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}

	res.resize(n, 0);
	dfs(0);
	if(!found) {
		return res;
	}

	vector<pair<int, int>> vec = { make_pair(a, 1), make_pair(b, 2), make_pair(c, 3) };
	sort(vec.begin(), vec.end());

	int cnt[3] = {0, 0, 0}, rep[3] = {0, 0, 0};
	for(int i=0; i<n; ++i) {
		assert(res[i] != 0);
		cnt[res[i]]++;
		rep[res[i]] = i;
	}

	for(int nr=1; nr<=2; ++nr) {
		dfst(rep[nr]);
		vector<int> ready;
		for(int i=0; i<n; ++i) {
			if(res[i]==nr && deg[i]==1) {
				ready.push_back(i);
			}
		}
		while(cnt[nr] > vec[nr-1].first) {
			assert(ready.size());
			int cur = ready.back();
			ready.pop_back();
			res[cur] = 0;
			cnt[nr]--;
			for(int i: tree[cur]) {
				deg[i]--;
				if(deg[i]==1) {
					ready.push_back(i);
				}
			}
		}
	}

	int nrA = vec[0].second, nrB = vec[1].second, nrC = vec[2].second;
	
	for(int i=0; i<n; ++i) {
		if(res[i]==1) {
			res[i] = nrA;
		}
		else if(res[i]==2) {
			res[i] = nrB;
		}
		else {
			res[i] = nrC;
		}
	}
	
	return res;
}

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