test/yosupo-judge/persistent_unionfind/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_unionfind
• Link: View error logs on GitHub Actions

Depends on

• Persistent array (Mylib/DataStructure/Array/persistent_array.cpp)
• Persistent union-find (Mylib/DataStructure/UnionFind/persistent_unionfind.cpp)
• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuples with index (Mylib/IO/input_tuples_with_index.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#include <iostream>
#include <vector>
#include "Mylib/DataStructure/UnionFind/persistent_unionfind.cpp"
#include "Mylib/IO/input_tuples_with_index.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  std::vector<hl::persistent_unionfind> G(Q + 1);

  G[0] = hl::persistent_unionfind(N);

  for (auto [i, t, k, u, v] : hl::input_tuples_with_index<int, int, int, int>(Q)) {
    ++k;
    ++i;

    if (t == 0) {
      G[i] = G[k].merge(u, v);
    } else {
      std::cout << G[k].is_same(u, v) << "\n";
    }
  }

  return 0;
}

#line 1 "test/yosupo-judge/persistent_unionfind/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#include <iostream>
#include <vector>
#line 3 "Mylib/DataStructure/Array/persistent_array.cpp"
#include <memory>
#line 5 "Mylib/DataStructure/Array/persistent_array.cpp"

namespace haar_lib {
  template <typename T>
  class persistent_array {
  public:
    using value_type = T;

  private:
    struct node {
      bool is_terminal;
      int size   = 1;
      node *left = nullptr, *right = nullptr;
      std::unique_ptr<T> value;

      node() : is_terminal(false) {}
      node(T v) : is_terminal(true), value(new T(v)) {}
    };

    size_t size_;
    int depth_;
    node *root_ = nullptr;

    int get_size(node *t) const {
      return t ? t->size : 0;
    }

    node *init(int s, int d) {
      if (s == 0) return nullptr;
      if (d == depth_) {
        return new node(T());
      } else {
        node *t  = new node();
        t->left  = init(s / 2, d + 1);
        t->right = init(s - s / 2, d + 1);
        t->size  = get_size(t->left) + get_size(t->right);
        return t;
      }
    }

    void apply_init(node *t, const std::vector<T> &ret, int &i) {
      if (not t) return;

      if (t->is_terminal) {
        *(t->value) = ret[i];
        ++i;
        return;
      }

      apply_init(t->left, ret, i);
      apply_init(t->right, ret, i);
    }

    persistent_array(node *root) : root_(root) {}

    void calc_depth() {
      depth_ = 1;
      while ((int) size_ > (1 << depth_)) depth_ += 1;
      depth_ += 1;
    }

  public:
    persistent_array() {}
    persistent_array(size_t size) : size_(size) {
      calc_depth();
      root_ = init(size_, 1);
    }

    persistent_array(const std::vector<T> &v) : size_(v.size()) {
      calc_depth();
      root_ = init(size_, 1);

      int i = 0;
      apply_init(root_, v, i);
    }

    persistent_array(const persistent_array &v) {
      this->root_  = v.root_;
      this->size_  = v.size_;
      this->depth_ = v.depth_;
    }

  protected:
    T get(node *t, int i) const {
      if (t->is_terminal) return *(t->value);

      int k = get_size(t->left);
      if (i < k)
        return get(t->left, i);
      else
        return get(t->right, i - k);
    }

  public:
    T operator[](int i) const {
      return get(root_, i);
    }

  protected:
    node *set(node *prev, int i, const T &val) const {
      if (prev->is_terminal) return new node(val);

      int k = get_size(prev->left);

      node *t = new node();
      if (i < k) {
        t->right = prev->right;
        t->left  = set(prev->left, i, val);
        t->size  = get_size(t->right) + get_size(t->left);
      } else {
        t->left  = prev->left;
        t->right = set(prev->right, i - k, val);
        t->size  = get_size(t->right) + get_size(t->left);
      }
      return t;
    }

  public:
    persistent_array set(int i, const T &val) const {
      node *ret = set(root_, i, val);
      return persistent_array(ret);
    }

  protected:
    void traverse(node *t, std::vector<T> &ret) const {
      if (not t) return;

      if (t->is_terminal) {
        ret.push_back(*(t->value));
        return;
      }

      traverse(t->left, ret);
      traverse(t->right, ret);
    }

  public:
    std::vector<T> data() const {
      std::vector<T> ret;
      traverse(root_, ret);
      return ret;
    }
  };
}  // namespace haar_lib
#line 4 "Mylib/DataStructure/UnionFind/persistent_unionfind.cpp"

namespace haar_lib {
  class persistent_unionfind {
    persistent_array<int> par_;

    persistent_unionfind(persistent_array<int> par) : par_(par) {}

  public:
    persistent_unionfind() {}
    persistent_unionfind(int n) : par_(persistent_array<int>(std::vector<int>(n, -1))) {}

    int root_of(int i) const {
      const int p = par_[i];
      if (p < 0) return i;
      return root_of(p);
    }

    bool is_same(int i, int j) const {
      return root_of(i) == root_of(j);
    }

    int size_of(int i) const {
      return -par_[root_of(i)];
    }

    persistent_unionfind merge(int i, int j) const {
      const int ri = root_of(i), rj = root_of(j);
      if (ri == rj) return *this;

      const int size_i = -par_[ri];
      const int size_j = -par_[rj];

      persistent_array<int> ret = par_;

      if (size_i > size_j) {
        ret = ret.set(ri, -(size_i + size_j));
        ret = ret.set(rj, ri);
      } else {
        ret = ret.set(rj, -(size_i + size_j));
        ret = ret.set(ri, rj);
      }

      return persistent_unionfind(ret);
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuples_with_index.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples_with_index.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples_with_index.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuplesWithIndex {
    struct iter {
      using value_type = std::tuple<int, Args...>;
      value_type value;
      bool fetched = false;
      int N;
      int c = 0;

      value_type operator*() {
        if (not fetched) {
          std::tuple<Args...> temp;
          std::cin >> temp;
          value = std::tuple_cat(std::make_tuple(c), temp);
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuplesWithIndex(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples_with_index(int N) {
    return InputTuplesWithIndex<Args...>(N);
  }
}  // namespace haar_lib
#line 7 "test/yosupo-judge/persistent_unionfind/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  std::vector<hl::persistent_unionfind> G(Q + 1);

  G[0] = hl::persistent_unionfind(N);

  for (auto [i, t, k, u, v] : hl::input_tuples_with_index<int, int, int, int>(Q)) {
    ++k;
    ++i;

    if (t == 0) {
      G[i] = G[k].merge(u, v);
    } else {
      std::cout << G[k].is_same(u, v) << "\n";
    }
  }

  return 0;
}

Back to top page