Submission #830488

#TimeUsernameProblemLanguageResultExecution timeMemory
830488caganyanmazThousands Islands (IOI22_islands)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define mp(x...) array<int, 2>({x}) #define pb push_back #include "islands.h" using namespace std; #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif 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>> res; vector<array<int, 2>> g[MXN]; bool dfs(int node, int le) { res.pb(mp(node, le)); visited[node] = true; for (auto [c, e] : g[node]) { debug(node, c, e, le); if ((e/2) == (le/2)) continue; if (visited[c]) { res.pb({c, e}); return true; } else if (dfs(c, e)) { return true; } } res.pop_back(); 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 < m; i++) { debug(i, u[i], v[i]); g[u[i]].pb(mp(v[i], i)); } if(dfs(0, -2)) { vector<int> out; debug(res); int lsn = res.back()[0]; // Go to the loop int i = 0; do { if (i != 0) out.pb(res[i][1]); } while (res[i][0] != lsn); if (i != 0) out.pb(res[i][1]); debug(out); // Cycle in loop for (int j = i+1; j < res.size(); j++) out.pb(res[j][1]); debug(out); // Cycle back in loop for (int j = res.size()-1; j > i; j--) out.pb(get_reverse(res[j][1])); debug(out); // Cycle in loop again for (int j = res.size()-1; j > i; j--) out.pb(res[j][1]); debug(out); // Cycle back again for (int j = i+1; j < res.size(); j++) out.pb(get_reverse(res[j][1])); debug(out); // Come back for (int j = i; j >= 1; j--) out.pb(res[j][1]); debug(out); return out; } return false; } #include <bits/stdc++.h> #define mp(x...) array<int, 2>({x}) #define pb push_back #include "islands.h" using namespace std; #define DEBUGGING #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif 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>> res; vector<array<int, 2>> g[MXN]; bool dfs(int node, int le) { res.pb(mp(node, le)); visited[node] = true; for (auto [c, e] : g[node]) { debug(node, c, e, le); if ((e/2) == (le/2)) continue; if (visited[c]) { res.pb({c, e}); return true; } else if (dfs(c, e)) { return true; } } res.pop_back(); 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 < m; i++) { debug(i, u[i], v[i]); g[u[i]].pb(mp(v[i], i)); } if(dfs(0, -2)) { vector<int> out; debug(res); int lsn = res.back()[0]; // Go to the loop int i = 0; do { if (i != 0) out.pb(res[i][1]); } while (res[i][0] != lsn); if (i != 0) out.pb(res[i][1]); debug(out); // Cycle in loop for (int j = i+1; j < res.size(); j++) out.pb(res[j][1]); debug(out); // Cycle back in loop for (int j = res.size()-1; j > i; j--) out.pb(get_reverse(res[j][1])); debug(out); // Cycle in loop again for (int j = res.size()-1; j > i; j--) out.pb(res[j][1]); debug(out); // Cycle back again for (int j = i+1; j < res.size(); j++) out.pb(get_reverse(res[j][1])); debug(out); // Come back for (int j = i; j >= 1; j--) out.pb(res[j][1]); debug(out); return out; } 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); } 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); }

Compilation message (stderr)

islands.cpp:116:10: fatal error: ../debug.h: No such file or directory
  116 | #include "../debug.h"
      |          ^~~~~~~~~~~~
compilation terminated.