Submission #1053054

#TimeUsernameProblemLanguageResultExecution timeMemory
1053054MercubytheFirstKeys (IOI21_keys)C++17
0 / 100
0 ms348 KiB
#include "keys.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; vector<signed> find_reachable(vector<signed> r, vector<signed> u, vector<signed> v, vector<signed> c) { int n = r.size(); int m = u.size(); vector<vector<pii> > g(n); for(int i = 0; i < m; ++i) { g[u[i]].push_back({v[i], c[i]}); g[v[i]].push_back({u[i], c[i]}); } vector<bool> vis, got_key; vector<vector<int> > waiting; auto reach_dfs = [&](auto&& dfs, int node) -> void { assert(node < n and node >= 0); if (vis[node]) { return; } vis[node] = true; // cout << "hi " << node << ' ' << r[node] << endl; got_key[r[node]] = true; while(!waiting[r[node]].empty()) { if(!vis[ waiting[r[node]].back() ]) { int to = waiting[r[node]].back(); waiting[r[node]].pop_back(); dfs(dfs, to); } else { waiting[r[node]].pop_back(); } } for(auto [to, key] : g[node]) { if(vis[to]) { continue; } else if(!got_key[key]) { assert(to < n); waiting[key].push_back(to); } else { dfs(dfs, to); } } }; vector<int> ans(n); for(int i = 0; i < n; ++i) { vis.assign(n, false); got_key.assign(m, false); waiting.assign(m, vector<int>()); reach_dfs(reach_dfs, i); ans[i] = count(vis.begin(), vis.end(), true); // cout << i << " : "; // for(int j = 0; j < n; ++j) // cout << vis[j] << ' '; // cout << " : "; // for(int j = 0; j < m; ++j) { // cout << got_key[j] << ' '; // } // cout << endl; } int mn = *min_element(ans.begin(), ans.end()); for(int& x : ans) x = (x == mn); return ans; } /* 7 10 0 1 1 2 2 1 2 0 1 0 0 2 0 1 2 1 1 3 0 2 3 0 3 4 1 3 5 2 4 5 0 4 6 2 5 6 1 */
#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...