Submission #415838

#	Time	Username	Problem	Language	Result	Execution time	Memory
415838		Mlxa	Split the Attractions (IOI19_split)	C++14	22 / 100	523 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;
mt19937 rnd;
int n;
vector<int> g[N];

int sz[N];

void dfs(int v, int p) {
	sz[v] = 1;
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		dfs(u, v);
		sz[v] += sz[u];
	}
}

void bfs(int v, int d[N]) {
	fill_n(d, n, INF);
	d[v] = 0;
	queue<int> q;
	q.push(v);
	while (q.size()) {
		v = q.front(); q.pop();
		for (int u : g[v]) {
			if (d[u] > d[v] + 1) {
				d[u] = d[v] + 1;
				q.push(u);
			}
		}
	}
}

int dv[N], du[N];

pair<vector<int>, vector<int>> solve(int v, int u) {
	bfs(v, dv), bfs(u, du);
	vector<int> pv, pu;
	for (int i = 0; i < n; ++i) {
		// cout << i << " " << dv[i] << " " << du[i] << endl;
		if (dv[i] < du[i]) {
			pv.push_back(i);
		} else {
			pu.push_back(i);
		}
	}
	sort(all(pv), [&](int i, int j) {
		return dv[i] < dv[j];
	});
	sort(all(pu), [&](int i, int j) {
		return du[i] < du[j];
	});
	return {pv, pu};
}
int small(int v, int u) {
	int t = min(sz[v], sz[u]);
	return min(t, n - t);
}
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	using namespace my;
	n = _n;
	int a0 = a, b0 = b, c0 = c;
	vector<int> tmp = {a, b, c};
	sort(all(tmp));
	a = tmp[0], b = tmp[1], c = tmp[2];
	for (int i = 0; i < (int)p.size(); ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	dfs(0, 0);
	vector<int> res(n, 0);
	int tv = -1, tu = -1;
	for (int i = 0; i < n; ++i) {
		for (int j : g[i]) {
			int cur = small(i, j);
			if (a <= cur && cur <= a + c) {
				tv = i, tu = j;
			}
		}
	}
	if (tv != -1) {
		int v = tv, u = tu;
		tie(p, q) = solve(v, u);
		// cout << "solved " << v << " " << u << endl;
		// for (int e : p) cout << e << " "; cout << endl;
		// for (int e : q) cout << e << " "; cout << endl;
		if (p.size() > q.size()) {
			swap(p, q);
		}
		// cout << p.size() << " " << q.size() << endl;
		if ((int)p.size() < a || (int)p.size() > a + c) {
			assert(false);
		}
		assert((int)p.size() >= a && (int)q.size() >= b);
		fill(all(res), 3);
		for (int i = 0; i < a; ++i) {
			res[p[i]] = 1;
		}
		for (int i = 0; i < b; ++i) {
			res[q[i]] = 2;
		}
		if (a == a0 && b == b0 && c == c0) {
			;
		} else if (a == a0 && b == c0 && c == b0) {
			for (int &e : res) {
				if (e == 1) {
					e = 1;
				} else if (e == 2) {
					e = 3;
				} else {
					assert(e == 3);
					e = 2;
				}
			}
		} else if (a == b0 && b == a0 && c == c0) {
			for (int &e : res) {
				if (e == 1) {
					e = 2;
				} else if (e == 2) {
					e = 1;
				} else {
					assert(e == 3);
					e = 3;
				}
			}
		} else if (a == b0 && b == c0 && c == a0) {
			for (int &e : res) {
				if (e == 1) {
					e = 2;
				} else if (e == 2) {
					e = 3;
				} else {
					assert(e == 3);
					e = 1;
				}
			}
		} else if (a == c0 && b == a0 && c == b0) {
			for (int &e : res) {
				if (e == 1) {
					e = 3;
				} else if (e == 2) {
					e = 1;
				} else {
					assert(e == 3);
					e = 2;
				}
			}
		} else if (a == c0 && b == b0 && c == a0) {
			for (int &e : res) {
				if (e == 1) {
					e = 3;
				} else if (e == 2) {
					e = 2;
				} else {
					assert(e == 3);
					e = 1;
				}
			}
		} else {
			assert(false);
		}
		assert((int)count(all(res), 1) == a0);
		assert((int)count(all(res), 2) == b0);
		assert((int)count(all(res), 3) == c0);
		return res;
	}
	return res;
}

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

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