Submission #836401

#TimeUsernameProblemLanguageResultExecution timeMemory
836401SamAndThousands Islands (IOI22_islands)C++17
31 / 100
27 ms5204 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; 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); } 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 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:60: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]
   60 |             for (int i = 0; i < g[x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~
islands.cpp:94: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]
   94 |         for (int i = 0; i < g[0].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
islands.cpp:107: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]
  107 |         for (int i = 0; i < g[1].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
islands.cpp:116: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]
  116 |         for (int i = 0; i < g[2].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
#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...