Submission #1060830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060830		Gromp15	Keys (IOI21_keys)	C++17	37 / 100	3067 ms	66932 KiB

keys

#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct dsu {
	vector<int> p, size, got;
	dsu(int n, const vector<int>& r) : p(n), size(n, 1), got(n) {
		iota(all(p), 0);
		for (int i = 0; i < n; i++) got[i] = 1 << r[i];
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	bool merge(int a, int b) {
		a = get(a), b = get(b);
		if (a == b) return 0;
		if (size[a] < size[b]) swap(a, b);
		size[a] += size[b], got[a] |= got[b], p[b] = a;
		return 1;
	}
	int val(int v) {
		return got[get(v)];
	}
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = sz(r), m = sz(u);
	vector<vector<ar<int, 2>>> adj(n);
	for (int i = 0; i < m; i++) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	vector<set<int>> groups(n);
	for (int i = 0; i < n; i++) groups[i].insert(i);
	vector<int> col(n);
	int timer = 0;
	int mn = 1e9;
	vector<int> ans(n);
	while (1) {
		const int N = sz(groups);
		vector<int> who(n);
		for (int i = 0; i < N; i++) for (int x : groups[i]) who[x] = i;
		vector<vector<int>> adj2(N);
		for (int i = 0; i < N; i++) {
			timer++;
			for (int g : groups[i]) col[r[g]] = timer;
			for (int g : groups[i]) {
				for (auto [u, w] : adj[g]) {
					if (col[w] == timer && i != who[u]) {
						adj2[i].emplace_back(who[u]);
					}
				}
			}
		}
		for (int i = 0; i < N; i++) if (groups[i].size()) {
			if (adj2[i].empty()) {
				if (ckmin(mn, sz(groups[i]))) {
					fill(all(ans), 0);
					for (int g : groups[i]) ans[g] = 1;
				}
				else if (mn == sz(groups[i])) {
					for (int g : groups[i]) ans[g] = 1;
				}
			}
		}
		vector<int> tin(N), low(N), stk;
		vector<bool> vis(N);
		vector<set<int>> groups2;
		int timer2 = 0, comp = 0;
		auto dfs = [&](auto&& s, int v) -> void {
			tin[v] = low[v] = ++timer2;
			stk.emplace_back(v);
			for (int u : adj2[v]) if (!vis[u]) {
				if (!tin[u]) {
					s(s, u), ckmin(low[v], low[u]);
				}
				else ckmin(low[v], tin[u]);
			}
			if (tin[v] == low[v]) {
				groups2.push_back({});
				for (int x = -1; x != v; ) {
					x = stk.back(); stk.pop_back();
					vis[x] = 1;
					groups2.back().insert(x);
				}
				comp++;
			}
		};
		for (int i = 0; i < N; i++) if (!tin[i]) dfs(dfs, i);
		for (int i = 0; i < sz(groups2); i++) {
			set<int> cur;
			for (int p : groups2[i]) for (int x : groups[p]) {
				cur.insert(x);
			}
			swap(cur, groups2[i]);
		}
		swap(groups, groups2);
		if (sz(groups) == sz(groups2)) break;
	}
	return ans;
}

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