Submission #817045

#	Time	Username	Problem	Language	Result	Execution time	Memory
817045		KoD	Thousands Islands (IOI22_islands)	C++17	100 / 100	131 ms	19028 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

void append(vector<int>& a, vector<int> b) { copy(b.begin(), b.end(), back_inserter(a)); }
vector<int> cut(const vector<int>& a, int l, int r) { return vector<int>(a.begin() + l, a.begin() + r); }
vector<int> rev(const vector<int>& a) { return vector<int>(a.rbegin(), a.rend()); }

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
  const auto other = [&](int u, int e) { return U[e] ^ V[e] ^ u; };
  vector<vector<int>> G(N), rG(N);
  for (int i = 0; i < M; ++i) {
    G[U[i]].push_back(i);
    rG[V[i]].push_back(i);
  }
  vector<int> out(N);
  vector<char> dead(N);
  queue<int> que;
  const auto clean = [&] {
    while (!que.empty()) {
      const int u = que.front();
      que.pop();
      dead[u] = true;
      for (const int e : rG[u]) {
        const int v = other(u, e);
        if ((--out[v]) == 0) que.push(v);
      }
    }
  };
  for (int i = 0; i < N; ++i) {
    out[i] = (int)G[i].size();
    if (out[i] == 0) que.push(i);
  }
  clean();
  vector<int> path;
  for (int u = 0;;) {
    if (dead[u]) return false;
    vector<int> next;
    for (const int e : G[u]) {
      if (!dead[other(u, e)]) next.emplace_back(e);
    }
    if (next.size() >= 2) {
      vector<int> state(N), depth(N);
      vector<int> cycle1, cycle2;
      int length = -1;
      for (int v = u, e = next[0];;) {
        state[v] = 1;
        v = other(v, e);
        cycle1.push_back(e);
        if (state[v]) {
          append(cycle1, rev(cut(cycle1, 0, depth[v])));
          length = depth[v];
          break;
        } else {
          depth[v] = depth[other(v, e)] + 1;
          for (const int f : G[v]) {
            if (!dead[other(v, f)]) e = f;
          }
        }
      }
      vector<int> cycle;
      for (int v = u, e = next[1];;) {
        state[v] = 2;
        v = other(v, e);
        cycle2.push_back(e);
        if (state[v] == 1) {
          append(cycle, cycle1);
          append(cycle, cycle2);
          if (depth[v] <= length) {
            append(cycle, cut(cycle1, depth[v], length));
          } else {
            append(cycle, rev(cut(cycle1, length, depth[v])));
          }
          append(cycle, rev(cut(cycle1, depth[v], (int)cycle1.size() - length)));
          append(cycle, rev(cycle2));
          break;
        } else if (state[v] == 2) {
          append(cycle2, rev(cut(cycle2, 0, depth[v])));
          append(cycle, cycle1);
          append(cycle, cycle2);
          append(cycle, rev(cycle1));
          append(cycle, rev(cycle2));
          break;
        } else {
          depth[v] = depth[other(v, e)] + 1;
          for (const int f : G[v]) {
            if (!dead[other(v, f)]) e = f;
          }
        }
      }
      vector<int> ret;
      append(ret, path);
      append(ret, cycle);
      append(ret, rev(path));
      return ret;
    } else {
      out[u] = 0;
      que.push(u);
      clean();
      const int e = next[0];
      path.push_back(e);
      u = other(u, e);
    }
  }
}

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