Submission #1241165

#TimeUsernameProblemLanguageResultExecution timeMemory
1241165MarwenElarbiThousands Islands (IOI22_islands)C++17
1.75 / 100
96 ms29512 KiB
#include <bits/stdc++.h> #include "islands.h" using namespace std; #define fi first #define se second #define pb push_back const int nax = 1e5+5; multiset<int> adj[nax]; multiset<int> revadj[nax]; int outdeg[nax]; bool vis[nax]; bool nabba[nax]; bool test=false; void dfs(int x){ if(vis[x]) return; vis[x]=true; for(auto u: adj[x]) dfs(u); } void dfs1(int x){ //cout <<x<<endl; if(nabba[x]) return; if(outdeg[x]>1) return; nabba[x]=true; if(outdeg[x]==1){ for(auto u:revadj[x]){ adj[u].erase(adj[u].count(x)); outdeg[u]--; } } for(auto u:adj[x]) dfs1(u); } std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) { int n = N; int m = M; for(int i = 0;i < m ; i++) { outdeg[U[i]]++; adj[U[i]].insert(V[i]); revadj[V[i]].insert(U[i]); } dfs(0); dfs1(0); for(int i = 0 ;i < n; i++) if(outdeg[i]>=2&&vis[i]&&!nabba[i]) test=true; return test; }
#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...