Submission #627259

#	Time	Username	Problem	Language	Result	Execution time	Memory
627259		model_code	Thousands Islands (IOI22_islands)	C++17	100 / 100	448 ms	33592 KiB

islands

// correct/solution-prabowo-ac.cpp
#include "islands.h"

#include <algorithm>
#include <functional>
#include <iterator>
#include <queue>
#include <utility>
#include <set>
#include <variant>
#include <vector>

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
  std::vector<std::set<std::pair<int, int>>> adj(N), radj(N);
  for (int j = 0; j < M; ++j) {
    adj[U[j]].emplace(V[j], j);
    radj[V[j]].emplace(U[j], j);
  }

  std::queue<int> q;
  for (int i = 0; i < N; ++i) {
    if (adj[i].empty()) {
      q.push(i);
    }
  }

  auto clearQueue = [&]() {
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto [v, j] : radj[u]) {
        adj[v].erase({u, j});
        if (adj[v].empty()) {
          q.push(v);
        }
      }
      radj[u].clear();
    }
  };

  std::vector<int> ans, beforeCycle;
  for (int u = 0;;) {
    clearQueue();
    if (adj[u].empty()) {
      return false;
    }

    if (static_cast<int>(adj[u].size()) == 1) {
      auto [v, j] = *adj[u].begin();
      ans.push_back(j);
      beforeCycle.push_back(j);
      radj[v].erase({u, j});
      adj[u].clear();
      q.push(u);
      u = v;
      continue;
    }

    for (int i = 0; i < N; ++i) {
      if (i != u && static_cast<int>(adj[i].size()) > 1) {
        adj[i].erase(std::next(adj[i].begin()), adj[i].end());
      }
    }
    adj[u].erase(std::next(adj[u].begin(), 2), adj[u].end());

    int invertCount = 0;
    std::vector<int> inverted(M);
    int lstEdge = -1;
    do {
      auto [v, j] = *adj[u].begin();
      if (lstEdge != -1) {
        adj[U[lstEdge]].emplace(V[lstEdge], lstEdge);
      }

      ans.push_back(j);

      lstEdge = j;
      adj[U[j]].erase({V[j], j});
      std::swap(U[j], V[j]);
      if (inverted[j] ^= 1) {
        ++invertCount;
      } else {
        --invertCount;
      }

      u = v;
    } while (invertCount != 0);
    break;
  }

  while (!beforeCycle.empty()) {
    ans.push_back(beforeCycle.back());
    beforeCycle.pop_back();
  }

  return ans;
}

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