Submission #816810

#	Time	Username	Problem	Language	Result	Execution time	Memory
816810		KoD	Thousands Islands (IOI22_islands)	C++17	10.85 / 100	29 ms	5304 KiB

islands

#include "islands.h"

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

template <class F> struct make_fixed : private F {
  explicit make_fixed(F&& f) : F(std::forward<F>(f)) {}
  template <class... Args> decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class T, class... Args> void DBG(const T& x, const Args&... args) {
  std::cerr << x;
  if constexpr (sizeof...(args)) {
    std::cerr << ' ';
    DBG(args...);
  } else {
    std::cerr << std::endl;
  }
}

template <class T> void DBG(const vector<T>& v) {
  std::cerr << '[';
  bool f = false;
  for (const T& x : v) {
    if (f) std::cerr << ", ";
    f = true;
    std::cerr << x;
  }
  std::cerr << ']' << std::endl;
}

std::variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
  vector<vector<int>> G(N), rG(N);
  for (int i = 0; i < M; ++i) {
    G[U[i]].push_back(V[i]);
    rG[V[i]].push_back(U[i]);
  }
  vector<char> dead(N);
  vector<int> out(N);
  const auto kill = make_fixed([&](auto&& kill, int u) -> void {
    if (dead[u]) return;
    dead[u] = true;
    vector<int> next;
    for (const int v : rG[u]) {
      if ((--out[v]) == 0) next.push_back(v);
    }
    for (const int v : next) kill(v);
  });
  for (int i = 0; i < N; ++i) {
    out[i] = (int)G[i].size();
    if (out[i] == 0) kill(i);
  }
  for (int u = 0, w;; u = w) {
    if (dead[u]) return false;
    w = -1;
    for (const int v : G[u]) {
      if (!dead[v]) {
        if (w == -1) w = v;
        else return true;
      }
    }
    if (w == -1) return false;
    kill(u);
  }
}

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