Submission #633222

#TimeUsernameProblemLanguageResultExecution timeMemory
633222tutisThousands Islands (IOI22_islands)C++17
0 / 100
1166 ms2097152 KiB
#include "islands.h" #include <variant> #include <vector> #include <bits/stdc++.h> using namespace std; variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { int s = 0; vector<bool> e(N, true); vector<int>ans0; { vector<int> C(N, 0); vector<int>b[N]; vector<int>ff[N]; for (int i = 0; i < M; i++) { C[U[i]]++; b[V[i]].push_back(U[i]); ff[U[i]].push_back(i); } stack<int>Q; for (int i = 0; i < N; i++) if (C[i] == 0) Q.push(i); while (e[s]) { if (C[s] == 1) { int s_ = -1; for (int ee : ff[s]) { if (e[V[ee]]) { ans0.push_back(ee); s_ = V[ee]; } } for (int t : b[s]) { if (e[t]) { C[t]--; if (C[t] == 0) Q.push(t); } } e[s] = false; s = s_; continue; } if (Q.empty()) break; int a = Q.top(); Q.pop(); if (!e[a]) continue; e[a] = false; for (int t : b[a]) { if (e[t]) { C[t]--; if (C[t] == 0) Q.push(t); } } } if (!e[s]) return false; } vector<int>adj[N]; vector<int>adj_[N]; for (int i = 0; i < M; i++) if (e[U[i]] && e[V[i]]) adj[U[i]].push_back(i); // for (int i = 0; i < N; i++) // if (i != s) // while (adj[i].size() > 1) // adj[i].pop_back(); // while (adj[s].size() > 2) // adj[s].pop_back(); for (int i = 0; i < N; i++) for (int e : adj[i]) { adj_[V[e]].push_back(e); } vector<int>ret = ans0; int ss = 0; vector<bool> state(M, false); bool fnd = false; function<void(int, int)> dfs = [&](int i, int e)->void { if (i == s && e != -1 && ss == 0) { fnd = true; return; } for (int ee : adj[i]) { int j = V[ee]; if (e == ee || state[ee] == true) continue; state[ee] = true; ret.push_back(ee); ss++; dfs(j, ee); ss--; if (fnd) return; ret.pop_back(); state[ee] = false; } for (int ee : adj_[i]) { int j = U[ee]; if (e == ee || state[ee] == false) continue; state[ee] = false; ss--; ret.push_back(ee); dfs(j, ee); if (fnd) return; ss++; ret.pop_back(); state[ee] = true; } }; dfs(s, -1); reverse(ans0.begin(), ans0.end()); for (int i : ans0) ret.push_back(i); if (!fnd) return false; return ret; }
#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...