Submission #1072394

#TimeUsernameProblemLanguageResultExecution timeMemory
1072394c2zi6Thousands Islands (IOI22_islands)C++17
11.90 / 100
31 ms8540 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "islands.h" int n, m; VVPI gp; stack<PII> st; VI onstack, vis, visedge; VI path, cycle; int zerocycle = -1; bool dfs(int u = 0, int pi = -1) { /*cout << "currently at " << u << endl;*/ for (auto[v, i] : gp[u]) if (i != pi && !visedge[i]) { /*cout << "trying to move to " << v << " via edge " << i << endl;*/ if (onstack[v]) { /*cout << "CYCLE DETECTED" << endl;*/ cycle.pb(i); while (st.size()) { if (st.top().ff == v) break; if (st.top().ff == 0) zerocycle = st.top().ss; cycle.pb(st.top().ss); st.pop(); } while (st.size()) { path.pb(st.top().ss); st.pop(); } reverse(all(path)); reverse(all(cycle)); /*for (int x : path) cout << x << " "; cout << "| ";*/ /*for (int x : cycle) cout << x << " "; cout << endl;*/ return true; } if (vis[v]) continue; /*cout << "moved successfully" << endl;*/ vis[v] = true; onstack[v] = true; st.push({v, i}); visedge[i] = true; if (dfs(v, i)) return true; onstack[v] = false; } return false; } VI rev(VI a) { reverse(all(a)); return a; } int myus(int x) { int type = !(x%2); return x/2*2+type; } variant<bool, VI> find_journey(int N, int M, VI U, VI V) { n = N; m = M; gp = VVPI(n); rep(i, m) gp[U[i]].pb({V[i], i}); onstack = vis = VI(n); visedge = VI(m); if (dfs()); else return false; VI ans; for (int x : path) ans.pb(x); for (int x : cycle) ans.pb(x); for (int x : rev(path)) ans.pb(x); if (zerocycle) { reverse(all(cycle)); int c = cycle.size(); int s = -1; rep(i, c) { cycle.pb(cycle[i]); if (cycle[i] == zerocycle) s = i; } replr(i, s, s+c-1) ans.pb(cycle[i]); } else { path[0] = myus(path[0]); for (int x : path) ans.pb(x); for (int x : rev(cycle)) ans.pb(x); for (int x : rev(path)) ans.pb(x); } return ans; }
#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...