Submission #630004

#TimeUsernameProblemLanguageResultExecution timeMemory
630004CauchicoThousands Islands (IOI22_islands)C++17
0 / 100
3 ms596 KiB
#include <bits/stdc++.h> using namespace std; int n,m; vector<vector<pair<int,int>>> adj,adj_rev; vector<bool> used,valid,bused; vector<int> order, component; void dfs1(int v) { used[v] = true; for (auto u : adj[v]) if (!used[u.first]) dfs1(u.first); order.push_back(v); } void dfs2(int v) { used[v] = true; component.push_back(v); for (auto u : adj_rev[v]) if (!used[u.first]) dfs2(u.first); } bool dfs3(int v, int b) { bused[b] = true; if (valid[v]) { return true; } for (auto u: adj[v]) { if (!bused[u.second]) { if (dfs3(u.first,u.second)) { return true; } } } return false; } bool find_journey(int N, int M, vector<int> U, vector<int> V) { n = N; m = M; adj.resize(n); adj_rev.resize(n); used.resize(n); valid.resize(n); bused.resize(m); for (int i=0;i<m;i++) { adj[U[i]].push_back({V[i],i}); adj_rev[V[i]].push_back({U[i],i}); } for (int i = 0; i < n; i++) if (!used[i]) dfs1(i); used.assign(n, false); reverse(order.begin(), order.end()); for (auto v : order) { if (!used[v]) { dfs2 (v); if (component.size() > 1) { for (auto k: component) { valid[k] = true; } } component.clear(); } } int cnt = 0; for (auto u: adj[0]) { cnt += dfs3(u.first,u.second); } if (cnt >= 2) { return true; } else { return false; } }
#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...