Submission #558379

#	Time	Username	Problem	Language	Result	Execution time	Memory
558379		teraqqq	Keys (IOI21_keys)	C++17	100 / 100	2106 ms	374340 KiB

keys

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <limits>

using namespace std;
using vi = vector<int>;

struct DsuStrong {
	vector<map<int, vi>> edg;
	vector<set<int>> keys;
	vector<queue<int>> q;
	vector<int> rnk, par;

	DsuStrong(int n) : edg(n), keys(n), q(n), rnk(n, 1), par(n) {
		iota(par.begin(), par.end(), 0);
	}

	int root(int v) {
		return v == par[v] ? v : par[v] = root(par[v]);
	}

	bool same(int a, int b) {
		return root(a) == root(b);
	}

	int any_edge(int v) {
		v = root(v);
		while (!q[v].empty()) {
			int u = root(q[v].front());
			q[v].pop();
			if (u != v) return u;
		}
		return -1;
	}

	bool unite(int a, int b) {
		a = root(a), b = root(b);
		if (a == b) {
			return false;
		} else {
			if (rnk[a] < rnk[b]) swap(a, b);
			rnk[a] += rnk[b];
			par[b] = a;

			for (int x : keys[b]) {
				auto [it, added] = keys[a].insert(x);
				if (added) {
					for (int u : edg[a][x]) q[a].push(u);
				}
			}

			for (auto [c, v] : edg[b]) {
				for (int x : v) edg[a][c].push_back(x);
				if (keys[a].count(c)) {
					for (int x : v) q[a].push(x);
				}
			}

			return true;
		}
	}
};

struct Dsu {
	vector<int> rnk, par;

	Dsu(int n) : rnk(n, 1), par(n) {
		iota(par.begin(), par.end(), 0);
	}

	int root(int v) {
		return v == par[v] ? v : par[v] = root(par[v]);
	}

	bool same(int a, int b) {
		return root(a) == root(b);
	}

	bool unite(int a, int b) {
		a = root(a), b = root(b);
		if (a == b) {
			return false;
		} else {
			if (rnk[a] < rnk[b]) swap(a, b);
			rnk[a] += rnk[b];
			par[b] = a;
			return true;
		}
	}
};

vi find_reachable(vi r, vi u, vi v, vi c) {
	const int n = r.size(), m = c.size();

	DsuStrong dsu_strong(n);
	Dsu dsu(n);

	for (int i = 0; i < n; ++i) {
		dsu_strong.keys[i].insert(r[i]);
	}

	for (int i = 0; i < m; ++i) {
		for (int t = 2; t--; ) {
			dsu_strong.edg[u[i]][c[i]].push_back(v[i]);
			if (r[u[i]] == c[i]) dsu_strong.q[u[i]].push(v[i]);
			swap(u[i], v[i]);
		}
	}

	vector<int> par(n, -1);
	queue<int> q; 
	for (int i = 0; i < n; ++i) q.push(i);

	while (!q.empty()) {
		const int v = q.front(); q.pop();
		const int u = dsu_strong.any_edge(v);
		// cout << "Pop v=" << v << ", with edge " << u << endl;
		if (u == -1) continue;


		if (dsu.same(v, u)) {
			for (int w = u; !dsu_strong.same(v, w); w = dsu_strong.root(par[w])) {
				dsu_strong.unite(w, v);
			}

			par[v] = v;
			int new_root = dsu_strong.root(v);
			par[new_root] = -1;
			q.push(new_root);
		} else {
			par[v] = u;
			dsu.unite(v, u);
			// cout << "unite " << u << " and " << v << " (tree)" << endl;
		}
	}

	vi roots, ans(n);

	int sz = numeric_limits<int>::max();

	for (int i = 0; i < n; ++i) {
		if (par[i] != -1) continue;
		int cur = dsu_strong.rnk[i];
		if (cur < sz) roots.clear(), sz = cur;
		if (cur == sz) roots.push_back(i);
	}

	vector<char> allowed(n);
	for (int x : roots) allowed[x] = true;

	for (int i = 0; i < n; ++i) {
		if (allowed[dsu_strong.root(i)]) ans[i] = 1;
	}

	return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33