Submission #830041

#	Time	Username	Problem	Language	Result	Execution time	Memory
830041		MadokaMagicaFan	Split the Attractions (IOI19_split)	C++14	0 / 100	3 ms	5204 KiB

split

#include "bits/stdc++.h"
#include "split.h"
using namespace std;
#define sz(v) ((int)(v).size())
#define pb push_back

const int N = 1e5;

int n, a, b, c;
int oa, ob, oc;

vector<array<int,2>> adj[N+5];
array<int, 2> bigg[N+5];
bitset<N+5> v;
bitset<2*N+5> og;
vector<int> va, vb, splist, p;

int dfs1(int x) {
	bigg[x] = {0,0};
	v[x] = 1;
	int l = 1;
	for (auto u : adj[x]) {
		if (v[u[0]]) continue;
		og[u[1]] = 1;
		p[u[0]] = x;
		int s = dfs1(u[0]);
		l += s;
		if (s > bigg[x][0])
			bigg[x] = {s, u[0]};
	}

	if (p[x] != x && n - l > bigg[x][0])
		bigg[x] = {n-l, p[x]};
	return l;
}

void dfs2(int x, vector<int> &vv) {
	v[x] = 1;
	vv.pb(x);
	for (auto u : adj[x]) {
		if (!og[u[1]]) continue;
		if (v[u[0]]) continue;
		dfs2(u[0], vv);
	}
}

void dfs3(int x, vector<int> &vv) {
	v[x] = 1;
	vv.pb(x);
	for (auto u : adj[x]) {
		if (!og[u[1]]) {
			splist.pb(u[0]);
			continue;
		}
		if (v[u[0]]) continue;
		dfs3(u[0], vv);
	}
}

int solve(int x) {
	v = 0;
	va.clear(); vb.clear(); splist.clear();

	if (bigg[x][0] >= b) {
		v[x] = 1;
		dfs2(bigg[x][1], vb);
		dfs2(x, va);
		return 1;
	} else if (p[x] != x) {
		v[x] = 1;
		dfs3(p[x], vb);
		while (sz(splist) && sz(vb) < b) {
			auto u = splist.back();
			splist.pop_back();
			if (v[u]) continue;
			dfs2(u, vb);
		}
		if (sz(vb) < b) return 0;
		dfs2(x, va);
		return 1;
	}
	return 0;
}

vector<int>
find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int>q)
{
	n = _n; a = _a; b = _b; c = _c;
	ob = a; oc = a+b;
	vector<int> ans(n, 0);
	p.assign(n+1, 0);

	if (c < b) { swap(b, c); swap(oc, ob); }
	if (c < a) { swap(a, c); swap(oa, oc); }
	if (b > a) { swap(a, b); swap(oa, ob); }
	/* c > a > b */

	for (int i = 0; i < sz(p); ++i) {
		adj[_p[i]].pb({q[i], i});
		adj[q[i]].pb({_p[i], i});
	}

	p[0] = 0;
	dfs1(0);
	
	vector<int> cntr;
	for (int i = 0; i < n; ++i) {
		if (bigg[i][0] <= n/2)
			cntr.pb(i);
	}

	assert(sz(cntr) > 0);
	if (solve(cntr[0])^1)
		return ans;

	// assert(sz(va) >= a);
	// assert(sz(vb) >= b);

	v = 0;
	for(int i = 0; i < b; ++i) {
		ans[i+ob] = vb[i];
		v[vb[i]] = 1;
	}

	for(int i = 0; i < a; ++i) {
		ans[i+oa] = va[i];
		v[va[i]] = 1;
	}

	for (int i = 0; i < n; ++i) {
		if (!v[i])
			ans[oc++] = i;
	}
	
	return ans;
}

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