Submission #1207971

#TimeUsernameProblemLanguageResultExecution timeMemory
1207971HappyCapybaraThousands Islands (IOI22_islands)C++20
0 / 100
19 ms6468 KiB
#include "islands.h" #include<bits/stdc++.h> using namespace std; vector<int> u, v; vector<vector<int>> g; vector<int> seen, es; 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 (es[next]) continue; es[next] = true; int nn = u[next]+v[next]-cur; if (seen[nn] == 2) continue; if (seen[nn] == 1){ if (nn == v[next]) c.push_back(next); else c.push_back(next+1); while (cur != nn){ if (cur == v[p[cur]]) c.push_back(p[cur]); else c.push_back(p[cur]+1); cur = u[p[cur]]+v[p[cur]]-cur; } while (cur != 0){ if (cur == v[p[cur]]) t.push_back(p[cur]); else t.push_back(p[cur]); cur = u[p[cur]]+v[p[cur]]-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); g[V[i]].push_back(i); } seen.resize(N, 0); es.resize(M, 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); reverse(c.begin(), c.end()); for (int x : c) res.push_back(x^1); for (int x : c) res.push_back(x); reverse(c.begin(), c.end()); 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...