#879404 (C++17) No.2346 Replace!!

提出ソース

結果

問題	No.2346 Replace!!
ユーザー	KoD
提出日時	2023-06-09 23:23:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	9,907 bytes
コンパイル時間	1,805 ms
コンパイル使用メモリ	152,236 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-10 14:31:50
合計ジャッジ時間	3,427 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	5 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	3 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	4 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	3 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	3 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	3 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	3 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	3 ms 5,376 KB
testcase_32	AC	3 ms 5,376 KB
testcase_33	AC	4 ms 5,376 KB
testcase_34	AC	3 ms 5,376 KB
testcase_35	AC	3 ms 5,376 KB
testcase_36	AC	3 ms 5,376 KB
testcase_37	AC	3 ms 5,376 KB
testcase_38	AC	3 ms 5,376 KB
testcase_39	AC	4 ms 5,376 KB
testcase_40	AC	3 ms 5,376 KB
testcase_41	AC	3 ms 5,376 KB
testcase_42	AC	3 ms 5,376 KB
testcase_43	AC	3 ms 5,376 KB
testcase_44	AC	3 ms 5,376 KB
testcase_45	AC	3 ms 5,376 KB
testcase_46	AC	3 ms 5,376 KB
testcase_47	AC	3 ms 5,376 KB
testcase_48	AC	3 ms 5,376 KB
testcase_49	AC	3 ms 5,376 KB
testcase_50	AC	3 ms 5,376 KB
testcase_51	AC	3 ms 5,376 KB
testcase_52	AC	3 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB
testcase_54	AC	3 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	3 ms 5,376 KB
testcase_57	AC	3 ms 5,376 KB
testcase_58	AC	2 ms 5,376 KB
testcase_59	AC	3 ms 5,376 KB
testcase_60	AC	3 ms 5,376 KB
testcase_61	AC	3 ms 5,376 KB
testcase_62	AC	3 ms 5,376 KB
testcase_63	AC	3 ms 5,376 KB
testcase_64	AC	3 ms 5,376 KB
testcase_65	AC	2 ms 5,376 KB
testcase_66	AC	3 ms 5,376 KB
testcase_67	AC	3 ms 5,376 KB
testcase_68	AC	3 ms 5,376 KB
testcase_69	AC	3 ms 5,376 KB
testcase_70	AC	2 ms 5,376 KB
testcase_71	AC	2 ms 5,376 KB
testcase_72	AC	3 ms 5,376 KB
testcase_73	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define MULTEST

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

namespace kod {
namespace util {

template <class F> class fixed_point : private F {
  constexpr fixed_point(F&& f) noexcept : F(std::forward<F>(f)) {}
  template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;

 public:
  template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
  using F = std::decay_t<G>;
  return fixed_point<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class forward_loop {
  int x, y;
  constexpr forward_loop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr forward_loop rep(int, int) noexcept;
  friend constexpr forward_loop rep(int) noexcept;

 public:
  constexpr forward_loop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return x++; }
};

[[nodiscard]] constexpr forward_loop rep(int l, int r) noexcept { return forward_loop(l, r); }
[[nodiscard]] constexpr forward_loop rep(int n) noexcept { return forward_loop(0, n); }

class backward_loop {
  int x, y;
  constexpr backward_loop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr backward_loop revrep(int, int) noexcept;
  friend constexpr backward_loop revrep(int) noexcept;

 public:
  constexpr backward_loop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return --x; }
};

[[nodiscard]] constexpr backward_loop revrep(int l, int r) noexcept { return backward_loop(r, l); }
[[nodiscard]] constexpr backward_loop revrep(int n) noexcept { return backward_loop(n, 0); }

template <class F> constexpr void repeat(int n, const F& f) noexcept {
  assert(n >= 0);
  while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

namespace stdio_impl {

template <class T> T scan() {
  T x;
  std::cin >> x;
  return x;
}
struct scan_any {
  template <class T> operator T() const { return scan<T>(); }
};

}  // namespace stdio_impl

template <class T = void> decltype(auto) scan() {
  if constexpr (std::is_same_v<T, void>) return stdio_impl::scan_any{};
  else return stdio_impl::scan<T>();
}
template <class T, std::size_t N> std::array<T, N> scan_arr() {
  std::array<T, N> a;
  for (auto& x : a) x = scan<T>();
  return a;
}
template <class T> std::vector<T> scan_vec(int n) {
  if (n == -1) n = scan<int>();
  assert(n >= 0);
  std::vector<T> v;
  v.reserve(n);
  while (n--) v.push_back(scan<T>());
  return v;
}

void flush() { std::cout << std::flush; }
void print() {}
template <class T, class... Args> void print(const T& x, const Args&... args) {
  std::cout << x;
  if (sizeof...(args) != 0) std::cout << ' ';
  print(args...);
}
template <class... Args> void println(const Args&... args) {
  print(args...);
  std::cout << '\n';
}
template <class C> void print_seq(const C& c, const char* sep = " ", const char* end = "\n") {
  bool f = false;
  for (const auto& x : c) {
    if (f) std::cout << sep;
    else f = true;
    std::cout << x;
  }
  std::cout << end;
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

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

using namespace util;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;

constexpr ll floor_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}

template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

void run();

}  // namespace sol
}  // namespace kod

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::fixed << std::setprecision(20);
  int cases = 1;
#ifdef MULTEST
  std::cin >> cases;
#endif
  while (cases--) kod::sol::run();
  return 0;
}

#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif

namespace kod {
namespace sol {

class Range {
  struct Iter {
    int itr;
    constexpr Iter(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
    constexpr int operator*() const noexcept { return itr; }
  };
  const Iter first, last;

 public:
  explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
  constexpr Iter begin() const noexcept { return first; }
  constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }

class UnionFind {
  int components;
  std::vector<int> data;

 public:
  explicit UnionFind(const int size = 0) : components(size), data(size, (int)-1) {}

  int size() const { return data.size(); }
  int count() const { return components; }

  int leader(const int u) {
    assert(0 <= u and u < size());
    return data[u] < 0 ? u : data[u] = leader(data[u]);
  }

  int size(const int u) {
    assert(0 <= u and u < size());
    return -data[leader(u)];
  }

  std::pair<int, bool> merge(int u, int v) {
    assert(0 <= u and u < size());
    assert(0 <= v and v < size());
    u = leader(u);
    v = leader(v);
    if (u == v) return std::make_pair(u, false);
    if (data[u] > data[v]) std::swap(u, v);
    components -= 1;
    data[u] += data[v];
    data[v] = u;
    return std::make_pair(u, true);
  }

  bool same(const int u, const int v) {
    assert(0 <= u and u < size());
    assert(0 <= v and v < size());
    return leader(u) == leader(v);
  }

  std::vector<std::vector<int>> decompose() {
    std::vector<int> buf(size()), len(size());
    for (const int i : rep(size())) len[buf[i] = leader(i)]++;
    std::vector<std::vector<int>> ret(size());
    for (const int i : rep(size())) ret[i].reserve(len[i]);
    for (const int i : rep(size())) ret[buf[i]].push_back(i);
    ret.erase(std::remove_if(ret.begin(), ret.end(), [&](const std::vector<int>& v) { return v.empty(); }), ret.end());
    return ret;
  }
};

void run() {
  const int n = scan();
  auto a = scan_vec<int>(n);
  auto b = scan_vec<int>(n);
  UnionFind dsu(n);
  vector<int> deg(n);
  for (const int i : rep(n)) {
    a[i] -= 1, b[i] -= 1;
    dsu.merge(i, a[i]);
    deg[a[i]] += 1;
  }

  vector<vector<int>> tree(n);
  vector<char> cycle(n);
  {
    std::queue<int> que;
    for (const int i : rep(n)) {
      if (deg[i] == 0) que.push(i);
    }
    while (!que.empty()) {
      const int u = que.front();
      que.pop();
      tree[a[u]].push_back(u);
      if ((--deg[a[u]]) == 0) que.push(a[u]);
    }
    for (const int i : rep(n)) {
      cycle[i] = (deg[i] > 0);
    }
  }
  vector<int> in(n), out(n);
  {
    int timer = 0;
    for (const int i : rep(n)) {
      if (cycle[i]) {
        make_fixed([&](auto&& dfs, const int u) -> void {
          in[u] = timer++;
          for (const int v : tree[u]) dfs(v);
          out[u] = timer++;
        })(i);
      }
    }
  }

  for (const int i : rep(n)) {
    if (!dsu.same(i, b[i])) {
      println("No");
      return;
    }
    if (cycle[i]) {
      if (!cycle[b[i]]) {
        println("No");
        return;
      }
    } else {
      if (!cycle[b[i]] && !(in[b[i]] < in[i] && out[i] < out[b[i]])) {
        println("No");
        return;
      }
    }
  }

  vector<char> done(n);
  std::fill(deg.begin(), deg.end(), 0);
  vector<int> next(n), prev(n);
  for (const int src : rep(n)) {
    if (!cycle[src] || done[src]) continue;
    vector<int> seq;
    for (int i = src; !done[i]; i = a[i]) {
      done[i] = true;
      seq.push_back(i);
    }
    const int m = (int)seq.size();
    for (const int i : rep(m)) {
      const int x = seq[i];
      const int y = seq[(i + 1) % m];
      next[x] = y;
      prev[y] = x;
    }
    for (const int i : seq) deg[b[i]] += 1;
    std::queue<int> que;
    for (const int i : seq) {
      if (deg[i] == 0) que.push(i);
    }
    while (!que.empty()) {
      const int i = que.front();
      que.pop();
      const int l = prev[i];
      const int r = next[i];
      next[l] = r;
      prev[r] = l;
      if ((--deg[b[i]]) == 0) {
        que.push(b[i]);
      }
    }
    for (const int i : seq) {
      if (deg[i] > 0 && next[i] != b[i]) {
        println("No");
        return;
      }
    }
  }

  println("Yes");
}

}  // namespace sol
}  // namespace kod

yukicoder

結果

テストケース

ソースコード