Submission #1207965

#TimeUsernameProblemLanguageResultExecution timeMemory
1207965HappyCapybaraThousands Islands (IOI22_islands)C++20
24 / 100
21 ms5828 KiB
#include "islands.h" #include<bits/stdc++.h> using namespace std; vector<int> u, v; vector<vector<int>> g; vector<int> seen; vector<int> p, t, c; void dfs(int cur){ if (!c.empty()) return; seen[cur] = 1; for (int next : g[cur]){ if (!c.empty()) return; if (seen[v[next]] == 2) continue; if (seen[v[next]] == 1){ c.push_back(next); while (cur != v[next]){ c.push_back(p[cur]); cur = u[p[cur]]; } while (cur != 0){ t.push_back(p[cur]); cur = u[p[cur]]; } reverse(c.begin(), c.end()); reverse(t.begin(), t.end()); return; } if (seen[v[next]] == 0){ p[v[next]] = next; dfs(v[next]); } } seen[cur] = 2; } variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){ u = U; v = V; g.resize(N); for (int i=0; i<M; i+=2){ g[U[i]].push_back(i); } seen.resize(N, 0); p.resize(N); dfs(0); if (c.empty()) return false; vector<int> res; for (int x : t) res.push_back(x); for (int x : c) res.push_back(x); for (int x : c) res.push_back(x+1); reverse(c.begin(), c.end()); for (int x : c) res.push_back(x); for (int x : c) res.push_back(x+1); reverse(t.begin(), t.end()); for (int x : t) res.push_back(x); return res; }
#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...