Submission #418380

#	Time	Username	Problem	Language	Result	Execution time	Memory
418380		Mlxa	Split the Attractions (IOI19_split)	C++14	0 / 100	538 ms	1048580 KiB

split

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "split.h"
 
using namespace std;
 
namespace my {
const int N = 1e5 + 10, INF = 1e9;
int A, B, C;
mt19937 rnd;
int n;
vector<int> g0[N], g[N];
bool used[N];
int hei[N];
int up[N];

void spa(int v, int p) {
	used[v] = true;
	for (int u : g0[v]) {
		if (u == p) {
			continue;
		}
		if (used[u]) {
			up[v] = min(up[v], hei[u]);
		} else {
			hei[u] = hei[v] + 1;
			g[v].push_back(u);
			g[u].push_back(v);
			spa(u, v);
			up[v] = min(up[v], up[u]);
		}
	}
}

int sz[N];
void get_sz(int v, int p) {
	sz[v] = 1;
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		get_sz(u, v);
		sz[v] += sz[u];
	}
}
int find_center(int v, int p) {
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		if (2 * sz[u] > n) {
			return find_center(u, v);
		}
	}
	return v;
}

int col[N];
void subcol(int v, int p) {
	col[v] = 1;
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		if (!col[u]) {
			subcol(u, v);
		}
	}
}

vector<int> find_answer() {
	// for (int i = 0; i < n; ++i) {
	// 	cout << col[i] << " ";
	// }
	// cout << endl;
	int cnt = (int)count(col, col + n, 1);
	assert(2 * cnt <= n);
	assert(cnt >= A && n - cnt >= B);
	vector<int> res(n, 3);
	int v = (int)(find(col, col + n, 1) - col);
	assert(v < n);
	queue<int> q;
	vector<int> order;
	q.push(v);
	vector<int> bfs(n, false);
	bfs[v] = true;
	while (q.size()) {
		v = q.front(); q.pop();
		order.push_back(v);
		for (int u : g[v]) {
			if (col[u] != 1) {
				continue;
			}
			if (!bfs[u]) {
				bfs[u] = true;
				q.push(u);
			}
		}
	}
	assert((int)order.size() == (int)count(col, col + n, 1));
	assert((int)order.size() >= A);
	for (int i = 0; i < A; ++i) {
		res[order[i]] = 1;
	}
	assert(q.empty());
	order.clear();
	bfs.assign(n, false);
	v = (int)(find(col, col + n, 0) - col);
	q.push(v);
	bfs[v] = true;
	while (q.size()) {
		v = q.front(); q.pop();
		order.push_back(v);
		for (int u : g[v]) {
			if (col[u] != 0) {
				continue;
			}
			if (!bfs[u]) {
				bfs[u] = true;
				q.push(u);
			}
		}
	}
	assert((int)order.size() == (int)count(col, col + n, 0));
	assert((int)order.size() >= B);
	for (int i = 0; i < B; ++i) {
		res[order[i]] = 2;
	}
	return res;
}
}
 
vector<int> solve(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	using namespace my;
	n = _n, A = _a, B = _b, C = _c;
	assert(A <= B && B <= C);
	for (int i = 0; i < (int)p.size(); ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	spa(0, 0);
	
	get_sz(0, 0);
	int cen = find_center(0, 0);
	get_sz(cen, cen);
	for (int v : g[cen]) {
		if (sz[v] >= A) {
			subcol(v, cen);
			return find_answer();
		}
	}
	vector<int> res(n, 0);
	if (!cen) {
		return res;
	}
	int least = sz[cen];
	for (int v : g[cen]) {
		if (sz[v] > sz[cen] || up[v] >= hei[cen]) {
			continue;
		}
		if (least - sz[v] >= A) {
			least -= sz[v];
			subcol(v, cen);
		}
	}
	if (least > A + C) {
		return res;
	}
	for (int i = 0; i < n; ++i) {
		col[i] ^= 1;
	}
	return find_answer();
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<pair<int, int>> srt = {{a, 1}, {b, 2}, {c, 3}};
	sort(all(srt));
	vector<int> res = solve(_n, srt[0].x, srt[1].x, srt[2].x, p, q);
	for (int &e : res) {
		e = srt[e - 1].y;
	}
	assert(count(all(res), 1) == a);
	assert(count(all(res), 2) == b);
	assert(count(all(res), 3) == c);
	return res;
}

#ifdef LC
#include "grader.cpp"
#endif

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