Submission #830592

#TimeUsernameProblemLanguageResultExecution timeMemory
830592caganyanmazThousands Islands (IOI22_islands)C++17
9.10 / 100
29 ms10184 KiB
#include <bits/stdc++.h> #define mp(x...) array<int, 2>({x}) #define pb push_back #include "islands.h" using namespace std; #define debug(x...) void(42) int n, m; vector<int> u, v; variant<bool, vector<int>> subtask1() { if (n <= 2) return false; array<array<int, 3>, 3> a; for (int i = 0; i < m; i++) if (u[i] <= 2 && v[i] <= 2) a[u[i]][v[i]] = i; debug(a); return vector<int>({a[0][1], a[1][2], a[2][0], a[0][2], a[2][1], a[1][0], a[2][0], a[1][2], a[0][1], a[1][0], a[2][1], a[0][2]}); } constexpr static int MXN = 1e5; bitset<MXN> visited; vector<array<int, 2>> g[MXN]; bool dfs(int node, int le) { visited[node] = true; if (g[node].size() > 2) return true; for (auto [c, e] : g[node]) { debug(node, c, e, le); if (e == le) continue; if (visited[c]) return true; else if (dfs(c, e)) return true; } return false; } static inline int get_reverse(int i) { return (i / 2) * 2 + 1 - (i&1); } variant<bool, vector<int>> subtask2() { for (int i = 0; i*2 < m; i++) { debug(i, u[i], v[i]); g[u[i*2]].pb(mp(v[i*2], i)); g[u[i*2+1]].pb(mp(v[i*2+1], i)); } if(dfs(0, -1) || g[0].size() > 1) return true; return false; } variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { n = N; m = M; u = U; v = V; return subtask2(); assert(false); }
#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...