제출 #1236356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236356		rxlfd314	수천개의 섬 (IOI22_islands)	C++20	38.10 / 100	106 ms	21320 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

variant<bool, vt<int>> find_journey(int N, int M, vt<int> U, vt<int> V) {
  if (N == 2) {
    vt<vt<int>> v(2);
    FOR(i, 0, M-1)
      v[U[i]].push_back(i);
    if (size(v[0]) < 2 || size(v[1]) < 1)
      return false;
    const int a = v[0][0], b = v[0][1], c = v[1][0];
    return vt<int>{a, c, b, a, c, b};
  }
  bool sub4 = true;
  REP(i, 0, M-2, 2)
    sub4 &= U[i] == U[i+1] && V[i] == V[i+1];
  if (!sub4) {
    map<ari2, vt<int>> pairs;
    vt<vt<int>> adj(N);
    REP(i, 0, M-2, 2) {
      pairs[{U[i], V[i]}].push_back(i);
      pairs[{V[i], U[i]}].push_back(i+1);
      adj[U[i]].push_back(V[i]);
      adj[V[i]].push_back(U[i]);
    }
    vt<int> ans, seen(N);
    const auto dfs = [&](auto &&self, const int i, const int p) -> bool {
      seen[i] = 1;
      for (const auto &j : adj[i]) {
        if (seen[j])
          continue;
        ans.push_back(pairs[{i, j}][0]);
        if (self(self, j, i))
          return true;
        ans.pop_back();
      }
      vt<int> va, vb;
      for (const auto &j : adj[i]) {
        if (j == p)
          continue;
        const ari2 bruh1 = {i, j}, bruh2 = {j, i};
        if (size(pairs[bruh1]) > 1) {
          va = {pairs[bruh1][0], pairs[bruh1][1]};
          vb = {pairs[bruh2][0], pairs[bruh2][1]};
          break;
        }
        if (size(pairs[bruh1])) {
          va.push_back(pairs[bruh1][0]);
          vb.push_back(pairs[bruh2][0]);
        }
        if (size(va) == 2)
          break;
      }
      if (size(va) == 2) {
        vt<int> v = {va[0], vb[0], va[1], vb[1], vb[0], va[0], vb[1], va[1]};
        ans.insert(ans.end(), all(v));
        return true;
      }
      return false;
    };
    if (dfs(dfs, 0, -1))
      return ans;
    return false;
  }
  if (sub4) {
    map<ari2, vt<int>> pairs;
    vt<vt<int>> adj(N);
    REP(i, 0, M-2, 2) {
      pairs[{U[i], V[i]}].push_back(i);
      pairs[{U[i], V[i]}].push_back(i+1);
      adj[U[i]].push_back(V[i]);
    }
    vt<int> ans, seen(N), par(N), in_cyc(N);
    const auto dfs = [&](auto &&self, const int i) -> bool {
      seen[i] = 1;
      for (const auto &j : adj[i]) {
        if (seen[j] == 2)
          continue;
        if (seen[j] == 1) {
          #ifdef DEBUG
          cout << "cycle:";
          for (int x = i; x != j; x = par[x])
            cout << ' ' << x;
          cout << ' ' << j << '\n';
          #endif
          vt<int> A = {pairs[{i, j}][0]}, B = {pairs[{i, j}][1]};
          for (int x = i; x != j; x = par[x]) {
            in_cyc[x] = 1;
            A.push_back(pairs[{par[x], x}][0]);
            B.push_back(pairs[{par[x], x}][1]);
            ans.pop_back();
          }
          in_cyc[j] = 1;
          reverse(all(A));
          reverse(all(B));
          ans.insert(ans.end(), all(A));
          ans.insert(ans.end(), all(B));
          reverse(all(A));
          reverse(all(B));
          ans.insert(ans.end(), all(A));
          ans.insert(ans.end(), all(B));
          return true;
        }
        ans.push_back(pairs[{i, j}][0]);
        par[j] = i;
        if (self(self, j)) {
          if (!in_cyc[i])
            ans.push_back(pairs[{i, j}][0]);
          return true;
        }
        ans.pop_back();
      }
      seen[i] = 2;
      return false;
    };
    if (dfs(dfs, 0)) {
      assert(size(ans) <= 2000000);
      return ans;
    }
    return false;
  }
  return false;
}

• Subtask 1: 5 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 24 / 24
• Subtask 5: 0 / 45