Submission #1209271

#TimeUsernameProblemLanguageResultExecution timeMemory
1209271banganKeys (IOI21_keys)C++20
37 / 100
3097 ms27600 KiB
#include <bits/stdc++.h> 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(); std::vector<std::vector<int>> adj(n); for (int i = 0; i < m; i++) { adj[u[i]].push_back(i); adj[v[i]].push_back(i); } std::vector<bool> vis(n), have(n); auto dfs = [&](auto self, int x) -> void { vis[x] = true; have[r[x]] = true; for (int i : adj[x]) { int y = v[i] ^ u[i] ^ x; if (!vis[y] && have[c[i]]) { self(self, y); } } }; std::vector<int> reach(n); for (int i = 0; i < n; i++) { std::fill(have.begin(), have.end(), false); int rep = 30; while (rep--) { fill(vis.begin(), vis.end(), false); dfs(dfs, i); } reach[i] = std::count(vis.begin(), vis.end(), true); } std::vector<int> ans(n); for (int i = 0; i < n; i++) { if (reach[i] == *std::min_element(reach.begin(), reach.end())) { ans[i] = 1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...