Submission #836415

#TimeUsernameProblemLanguageResultExecution timeMemory
836415SamAndThousands Islands (IOI22_islands)C++17
Compilation error
0 ms0 KiB
#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].fi; 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 (stderr)

islands.cpp: In function 'bool dfs(int)':
islands.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
islands.cpp:60:9: error: expected '}' before 'else'
   60 |         else if (!c[h])
      |         ^~~~
islands.cpp:27:9: note: to match this '{'
   27 |         {
      |         ^
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for (int i = 0; i < g[x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~
islands.cpp:174:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         for (int i = 0; i < g[0].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
islands.cpp:187:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |         for (int i = 0; i < g[1].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
islands.cpp:196:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         for (int i = 0; i < g[2].size(); ++i)
      |                         ~~^~~~~~~~~~~~~