Submission #415798

#	Time	Username	Problem	Language	Result	Execution time	Memory
415798		Mlxa	Split the Attractions (IOI19_split)	C++14	0 / 100	80 ms	11176 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];

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) {
		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};
}

}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	using namespace my;
	n = _n;
	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]);
	}
	vector<int> res(n, 0);
	for (int it = 0; it < 100; ++it) {
		int v = (int)(rnd() % n), u = (int)(rnd() % n);
		while (v == u) {
			v = (int)(rnd() % n), u = (int)(rnd() % n);
		}
		tie(p, q) = solve(v, u);
		if (p.size() > q.size()) {
			swap(p, q);
		}
		// cout << p.size() << " " << q.size() << endl;
		if ((int)p.size() < a || (int)p.size() > a + c) {
			continue;
		}
		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;
		}
		return res;
	}
	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