Submission #1241326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241326		trimkus	Keys (IOI21_keys)	C++20	39 / 100	660 ms	46816 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;



std::vector<int> find_reachable(std::vector<int> r, std::vector<int> _u, std::vector<int> _v, std::vector<int> _c) {
	int N = r.size();
	int M = _u.size();
	vector<vector<array<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<int> color(N);
	vector<int> scc(N);
	for (int i = 0; i < N; ++i) {
		color[i] |= (1 << r[i]);
	}
	vector<int> ret(N);
	for (int _ = 0; _ < 30; ++_) {
		int timer = 0;
		scc = vector<int>(N, 0);
		vector<int> state(N), tot(N + 1), out;
		auto dfs = [&](auto& dfs, int v) -> void {
			state[v] = 1;
			for (auto& [u, c] : adj[v]) {
				if (state[u] != 1 && (color[v] & (1 << c)) > 0) {
					dfs(dfs, u);
				}
			}
			out.push_back(v);

		};
		for (int i = 0; i < N; ++i) {
			if (state[i] == 0) {
				dfs(dfs, i);
			}
		}
		reverse(begin(out), end(out));
		auto rdfs = [&](auto& rdfs, int v) -> void {
			state[v] = 2;
			scc[v] = timer;
			tot[scc[v]] |= color[v];
			for (auto& [u, c] : adj[v]) {
				if (state[u] != 2 && (color[u] & (1 << c)) > 0) {
					rdfs(rdfs, u);
				}
			}
		};
		for (int it = 0; it < (int)out.size(); ++it) {
			int i = out[it];
			// cout << i << " -> ";
			if (state[i] != 2) {
				timer += 1;
				rdfs(rdfs, i);
			}
		}
		// cout << "\n";
		for (int i = 0; i < N; ++i) {
			color[i] = tot[scc[i]];
		}
		vector<int> valid(timer + 1, 1), sz(N);
		for (int i = 0; i < N; ++i) {
			for (auto& [u, c] : adj[i]) {
				if (((1 << c) & color[i]) > 0 && scc[i] != scc[u]) {
					valid[scc[i]] = 0; // sz[i] >= sz[i] + sz[scc[i]] > sz[scc[i]] => sz[i] != min(sz), i.e. we can go from scc[i] -> scc[u]
				}
			}
			sz[scc[i]] += 1;
		}
		// for (int i = 0; i < N; ++i) {
		// 	cout << scc[i] << " ";
		// }
		// cout << "\n";
		if (_ + 1 < 30) continue;
		int res = INT_MAX;
		for (int i = 1; i <= timer; ++i) {
			if (valid[i]) {
				res = min(res, sz[i]);
			}
		}
		// for (int i = 0; i < N; ++i) {
		// 	cout << scc[i] << " ";
		// }
		// cout << "\n";
		for (int i = 0; i < N; ++i) {
			ret[i] = (res == sz[scc[i]] && valid[scc[i]]);
		}
	}
	return ret;
}

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