Submission #1209275

#TimeUsernameProblemLanguageResultExecution timeMemory
1209275banganKeys (IOI21_keys)C++20
37 / 100
3092 ms25616 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<int> comp; std::vector<bool> vis(n), have(n); auto dfs = [&](auto self, int x) -> void { comp.push_back(x); 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++) { int rep = 1; while (rep--) { comp.clear(); dfs(dfs, i); for (int x : comp) { vis[x] = false; } } for (int x : comp) { have[r[x]] = false; } reach[i] = comp.size(); } int min = *std::min_element(reach.begin(), reach.end()); std::vector<int> ans(n); for (int i = 0; i < n; i++) { if (reach[i] == min) { 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...