Submission #1059479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059479		Gromp15	Keys (IOI21_keys)	C++17	37 / 100	3086 ms	25836 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; }

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<int> p(n);
	int mn = 1e9;
	for (int i = 0; i < n; i++) {
		vector<bool> vis(n), got(n);
		auto dfs = [&](auto&& s, int v) -> void {
			got[r[v]] = 1, vis[v] = 1;
			for (auto [u, col] : adj[v]) if (!vis[u] && got[col]) {
				s(s, u);
			}
		};
		dfs(dfs, i);
		for (int j = 0; j < n; j++) p[i] += vis[j];
		ckmin(mn, p[i]);
	}
	vector<int> ans(n);
	for (int i = 0; i < n; i++) ans[i] = p[i] == mn;
	return ans;
}

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