Submission #1194454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194454		jhwest2	Keys (IOI21_keys)	C++20	67 / 100	3088 ms	45868 KiB

keys

#include <vector>
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int SZ = 303030;
struct dsu {
	int par[SZ];
	int sz[SZ];
	void init() {
		iota(par, par + SZ, 0);
		fill(sz, sz + SZ, 1);
	}
	int find(int a) {
		return par[a] = par[a] == a ? a : find(par[a]);
	}
	void merge(int a, int b) {
		a = find(a);
		b = find(b);
		if (a != b) {
			sz[b] += sz[a];
			par[b] = a;
		}
	}
} dsu;
vector<int> find_reachable(vector<int> A, vector<int> U, vector<int> V, vector<int> B) {
	int n = A.size();
	int m = B.size();
	vector<pii> gph[n];
	for (int i = 0; i < m; i++) {
		gph[U[i]].push_back({i, V[i]});
		gph[V[i]].push_back({i, U[i]});
	}
	int ans[n]{};
	bool scc[n]{};
	int counter = 0;
	int key[n], chc[n];
	vector<pii> vec[n];
	fill(key, key + n, -1);
	fill(chc, chc + n, -1);	
	auto calc = [&](int v) {
		queue<int> Q;
		vector<int> vertices;
		Q.push(v);
		chc[v] = ++counter;
		int g = dsu.find(v);
		while (!Q.empty()) {
			int v = Q.front();
			Q.pop();
			if (dsu.find(v) != g) {
				v = dsu.find(v);
				assert(scc[v] || dsu.sz[v] >= dsu.sz[g]);
				dsu.merge(v, g);
				return;
			}
			vertices.push_back(v);
			int c = A[v];
			key[c] = counter;
			while (!vec[c].empty() && vec[c].back().ff == counter) {
				int x = vec[c].back().ss;
				vec[c].pop_back();
				if (chc[x] != counter) {
					Q.push(x);
					chc[x] = counter;
				}
			}
			for (auto [e, x] : gph[v]) {
				if (chc[x] != counter) {
					if (key[B[e]] == counter) {
						Q.push(x);
						chc[x] = counter;
					}
					else {
						vec[B[e]].push_back({counter, x});
					}
				}
			}
		}
		scc[g] = true;
		for (int v : vertices) ans[v] = vertices.size();
	};
	dsu.init();
	for (int v = 0; v < n; v++) {
		for (auto [e, x] : gph[v]) {
			if (B[e] == A[v]) {
				dsu.merge(x, v);
				break;
			}
		}
	}
	priority_queue<pii> pq;
	for (int v = 0; v < n; v++) {
		if (dsu.find(v) == v) {
			pq.push({-dsu.sz[v], v});
		}
	}
	while (!pq.empty()) {
		auto [sz, v] = pq.top();
		pq.pop();
		sz *= -1;
		if (dsu.sz[v] != sz || dsu.find(v) != v) {
			continue;
		}
		calc(v);
		int x = dsu.find(v);
		if (!scc[x]) {
			pq.push({-dsu.sz[x], x});
		}
	}
	int mn = 1e9;
	for (int v = 0; v < n; v++) {
		if (ans[v] != 0) mn = min(mn, ans[v]);
	}
	vector<int> ret(n);
	for (int v = 0; v < n; v++) {
		if (ans[v] == mn) ret[v] = 1;
	}
	return ret;
}

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