Submission #629015

#TimeUsernameProblemLanguageResultExecution timeMemory
629015abekerThousands Islands (IOI22_islands)C++17
53.85 / 100
411 ms50260 KiB
#include <bits/stdc++.h> #include "islands.h" using namespace std; typedef pair <vector <int>, vector <int>> pvv; vector <int> min_rot(vector <int> v) { rotate(v.begin(), min_element(v.begin(), v.end()), v.end()); return v; } variant <bool, vector <int>> find_journey(int N, int M, vector <int> u, vector <int> v) { queue <int> sinks; vector <unordered_set <int>> in(N), out(N); for (int i = 0; i < M; i++) { out[u[i]].insert(i); in[v[i]].insert(i); } auto refresh = [&](int x) { if (out[x].empty()) sinks.push(x); }; for (int i = 0; i < N; i++) refresh(i); int curr = 0; vector <int> sofar; while (1) { auto other = [&](int e, int x) { return u[e] ^ v[e] ^ x; }; auto remove = [&](int x) { for (auto it : in[x]) { int tmp = other(it, x); out[tmp].erase(it); refresh(tmp); } for (auto it : out[x]) in[other(it, x)].erase(it); }; for (; !sinks.empty(); sinks.pop()) { if (sinks.front() == curr) return false; remove(sinks.front()); } if (out[curr].size() == 1) { int edge = *out[curr].begin(); remove(curr); curr = other(edge, curr); sofar.push_back(edge); } else { auto find_cycle = [&](int x, int e, bool b) { int y = x; vector <int> path = {e}; vector <bool> bio(N); bio[x] = b; for (x = other(e, x); !bio[x]; x = other(e, x)) { path.push_back(e = *out[x].begin()); bio[x] = true; } bool flag = false; vector <int> tail, cycle; for (auto it : path) { flag |= y == x; if (flag) cycle.push_back(it); else tail.push_back(it); y = other(it, y); } return pvv(tail, cycle); }; auto it = out[curr].begin(); pvv cyc1 = find_cycle(curr, *it++, true); pvv cyc2 = find_cycle(curr, *it++, false); vector <int> sol; auto append = [&](vector <int> &v) { sol.insert(sol.end(), v.begin(), v.end()); reverse(v.begin(), v.end()); }; append(sofar); bool eq = min_rot(cyc1.second) == min_rot(cyc2.second); for (int i = 0; i < 2; i++) { auto traverse = [&](pvv &p1, pvv &p2) { append(p1.first); append(p1.second); if (eq) reverse(p2.second.begin(), p2.second.end()); append(p1.first); }; traverse(cyc1, cyc2); traverse(cyc2, cyc1); } append(sofar); return sol; } } }
#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...