# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
836418 | 2023-08-24T11:02:16 Z | SamAnd | Thousands Islands (IOI22_islands) | C++17 | 38 ms | 6136 KB |
#include "islands.h" #include <variant> #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) typedef long long ll; const int N = 1003, M = 200005; vector<pair<int, int> > g[N]; vector<int> ans; int c[N]; int pi[N]; int p[N]; bool dfs(int x) { c[x] = 1; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i].fi; int hi = g[x][i].se; if (c[h] == 1) { vector<int> s; int y = h; while (y) { s.push_back(pi[y]); y = p[y]; } reverse(all(s)); vector<int> v; y = x; while (y != h) { v.push_back(pi[y]); y = p[y]; } reverse(all(v)); v.push_back(hi); for (int i = 0; i < sz(s); ++i) ans.push_back(s[i]); for (int i = 0; i < sz(v); ++i) ans.push_back(v[i]); for (int i = 0; i < sz(v); ++i) ans.push_back((v[i] ^ 1)); for (int i = sz(v) - 1; i >= 0; --i) ans.push_back(v[i]); for (int i = sz(v) - 1; i >= 0; --i) ans.push_back((v[i] ^ 1)); for (int i = sz(s) - 1; i >= 0; --i) ans.push_back(s[i]); return true; } else if (!c[h]) { p[h] = x; pi[h] = hi; if (dfs(h)) return true; } } c[x] = 2; return false; } std::variant<bool, std::vector<int> > find_journey(int N, int M, std::vector<int> U, std::vector<int> V) { for (int i = 0; i < M; ++i) { g[U[i]].push_back(m_p(V[i], i)); } if (N == 2) { if (sz(g[0]) >= 2 && sz(g[1]) >= 1) { ans.push_back(g[0][0].se); ans.push_back(g[1][0].se); ans.push_back(g[0][1].se); ans.push_back(g[0][0].se); ans.push_back(g[1][0].se); ans.push_back(g[0][1].se); return ans; } return false; } bool z = true; if (M % 2 == 1) { z = false; } else { for (int i = 0; i < M; i += 2) { if (m_p(U[i], V[i]) != m_p(V[i + 1], U[i + 1])) { z = false; break; } } } if (z) { int x = 0; while (1) { vector<pair<int, int> > v; for (int i = 0; i < g[x].size(); ++i) { int h = g[x][i].fi; int hi = g[x][i].se; if (!ans.empty() && ans.back() / 2 == hi / 2) continue; v.push_back(m_p(h, hi)); } if (v.empty()) return false; if (sz(v) == 1) { ans.push_back(v[0].se); x = v[0].fi; continue; } vector<int> yans = ans; ans.push_back(v[0].se); ans.push_back((v[0].se ^ 1)); ans.push_back(v[1].se); ans.push_back((v[1].se ^ 1)); ans.push_back((v[0].se ^ 1)); ans.push_back(v[0].se); ans.push_back((v[1].se ^ 1)); ans.push_back(v[1].se); for (int i = sz(yans) - 1; i >= 0; --i) ans.push_back(yans[i]); return ans; } assert(false); } z = true; if (M % 2 == 1) { z = false; } else { for (int i = 0; i < M; i += 2) { if (m_p(U[i], V[i]) != m_p(U[i + 1], V[i + 1])) { z = false; break; } } } if (z) { if (!dfs(0)) return false; return ans; } else { int k0, k1, k2, k3; for (int i = 0; i < g[0].size(); ++i) { int h = g[0][i].fi; int hi = g[0][i].se; if (h == 1) { k0 = hi; } if (h == 2) { k1 = hi; } } for (int i = 0; i < g[1].size(); ++i) { int h = g[1][i].fi; int hi = g[1][i].se; if (h == 0) { k2 = hi; } } for (int i = 0; i < g[2].size(); ++i) { int h = g[2][i].fi; int hi = g[2][i].se; if (h == 0) { k3 = hi; } } ans.push_back(k0); ans.push_back(k2); ans.push_back(k1); ans.push_back(k3); ans.push_back(k2); ans.push_back(k0); ans.push_back(k3); ans.push_back(k1); return ans; } } /*int main() { int n, m; cin >> n >> m; vector<int> u, v; for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; u.push_back(x); v.push_back(y); } cout << find_journey(n, m, u, v) << "\n"; return 0; }*/ /* 5 6 0 1 1 0 1 3 3 1 0 4 4 0 3 6 0 1 1 0 1 2 2 1 2 0 0 2 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 232 KB | Output is correct |
5 | Correct | 1 ms | 248 KB | Output is correct |
6 | Correct | 0 ms | 256 KB | Output is correct |
7 | Correct | 27 ms | 5224 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 22 ms | 4656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 14 ms | 3040 KB | Output is correct |
18 | Correct | 17 ms | 2636 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 1 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 25 ms | 4656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 24 ms | 5096 KB | Output is correct |
4 | Correct | 29 ms | 5200 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 2 ms | 468 KB | Output is correct |
13 | Correct | 2 ms | 596 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 2 ms | 504 KB | Output is correct |
16 | Correct | 1 ms | 388 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 31 ms | 5764 KB | Output is correct |
21 | Correct | 25 ms | 5148 KB | Output is correct |
22 | Correct | 1 ms | 468 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 340 KB | Output is correct |
26 | Correct | 2 ms | 596 KB | Output is correct |
27 | Correct | 31 ms | 5700 KB | Output is correct |
28 | Correct | 30 ms | 5796 KB | Output is correct |
29 | Correct | 1 ms | 376 KB | Output is correct |
30 | Correct | 38 ms | 6136 KB | Output is correct |
31 | Correct | 0 ms | 340 KB | Output is correct |
32 | Correct | 29 ms | 5708 KB | Output is correct |
33 | Correct | 25 ms | 5272 KB | Output is correct |
34 | Correct | 14 ms | 3036 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 25 ms | 4788 KB | Output is correct |
37 | Correct | 26 ms | 5788 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 23 ms | 4872 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 29 ms | 6108 KB | Output is correct |
42 | Correct | 27 ms | 5784 KB | Output is correct |
43 | Correct | 1 ms | 340 KB | Output is correct |
44 | Correct | 1 ms | 340 KB | Output is correct |
45 | Correct | 2 ms | 596 KB | Output is correct |
46 | Correct | 11 ms | 2632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 232 KB | Output is correct |
5 | Correct | 1 ms | 248 KB | Output is correct |
6 | Correct | 0 ms | 256 KB | Output is correct |
7 | Correct | 27 ms | 5224 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 22 ms | 4656 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 0 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 212 KB | Output is correct |
25 | Correct | 1 ms | 340 KB | Output is correct |
26 | Correct | 1 ms | 212 KB | Output is correct |
27 | Correct | 0 ms | 212 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 212 KB | Output is correct |
30 | Correct | 14 ms | 3040 KB | Output is correct |
31 | Correct | 17 ms | 2636 KB | Output is correct |
32 | Correct | 0 ms | 212 KB | Output is correct |
33 | Correct | 0 ms | 212 KB | Output is correct |
34 | Correct | 1 ms | 212 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 25 ms | 4656 KB | Output is correct |
37 | Partially correct | 1 ms | 212 KB | Output is partially correct |
38 | Correct | 1 ms | 256 KB | Output is correct |
39 | Incorrect | 1 ms | 212 KB | Output isn't correct |
40 | Halted | 0 ms | 0 KB | - |