test/yosupo/persistent_unionfind.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_unionfind

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include "include/mtl/persistent_unionfind.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,q; cin>>n>>q;
    vector<PersistentUnionfind> U(q+1);
    for (int i = 0; i < q; i++) {
        int t; cin>>t;
        if (t == 0) {
            int k,u,v; cin>>k>>u>>v;
            U[i+1] = U[k+1].merge(u,v);
        } else {
            int k,u,v; cin>>k>>u>>v;
            cout << U[k+1].same(u,v) << endl;
        }
    }
}

#line 1 "test/yosupo/persistent_unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#line 2 "include/mtl/persistent_array.hpp"
#include <memory>
#include <utility>
#include <array>

template<typename T, unsigned Degree=4>
class PersistentArray {
  static constexpr unsigned M = Degree;
 private:
  struct Node;
  using node_ptr = std::shared_ptr<Node>;
  struct Node {
    T v;
    std::array<node_ptr, M> ch;
    Node() = default;
    explicit Node(const T& v) : v(v), ch({}) {}
    explicit Node(T&& v) : v(std::move(v)), ch({}) {}
  };
  node_ptr root_;
  T init_v_;
  explicit PersistentArray(node_ptr ptr, T init_v)
    : root_(ptr), init_v_(init_v) {}

 public:
  explicit PersistentArray(T init_v = T())
    : root_(nullptr), init_v_(init_v) {}

  bool empty() const { return root_ == nullptr; }
  T get(size_t i) const {
    auto u = root_;
    while (u and i > 0) {
      i--;
      u = u->ch[i % M];
      i /= M;
    }
    return u ? u->v : init_v_;
  }

 private:
  template<typename V>
  node_ptr set_rec(node_ptr u, size_t id, V&& v) const {
    if (id == 0) {
      if (u) {
        auto new_node = std::make_shared<Node>(*u);
        new_node->v = std::forward<V>(v);
        return new_node;
      } else {
        return std::make_shared<Node>(std::forward<V>(v));
      }
    } else {
      auto new_node = u ? std::make_shared<Node>(*u) : std::make_shared<Node>(init_v_);
      --id;
      new_node->ch[id % M] = set_rec(new_node->ch[id % M], id / M, std::forward<V>(v));
      return new_node;
    }
  }
 public:
  template<typename V>
  [[nodiscard]] PersistentArray set(size_t i, V&& v) const {
    static_assert(std::is_convertible<V, T>::value, "");
    return PersistentArray(set_rec(root_, i, std::forward<V>(v)), init_v_);
  }
  [[nodiscard]] PersistentArray set(size_t i, const T& v) const {
    return PersistentArray(set_rec(root_, i, v), init_v_);
  }
  [[nodiscard]] PersistentArray set(size_t i, T&& v) const {
    return PersistentArray(set_rec(root_, i, std::move(v)), init_v_);
  }
};
#line 3 "include/mtl/persistent_unionfind.hpp"
#include <cassert>

class PersistentUnionfind {
private:
    PersistentArray<long long> par_;
public:
    PersistentUnionfind() : par_(-1) {}
    size_t leader(size_t u) {
        auto pu = par_.get(u);
        if (pu < 0)
            return u;
        auto ret = leader(pu);
        par_ = par_.set(u, ret);
        return ret;
    }
    size_t size_of(size_t u) {
        return -par_.get(leader(u));
    }
    bool same(size_t a, size_t b) {
        return leader(a) == leader(b);
    }
    [[nodiscard]] PersistentUnionfind merge(size_t a, size_t b) {
        auto ra = leader(a);
        auto rb = leader(b);
        if (ra == rb)
            return *this;
        if (size_of(ra) < size_of(rb))
            std::swap(ra, rb);
        PersistentUnionfind ret = *this;
        ret.par_ = ret.par_.set(rb, ra);
        ret.par_ = ret.par_.set(ra, -(long long)(size_of(ra) + size_of(rb)));
        return ret;
    }
};
#line 4 "test/yosupo/persistent_unionfind.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,q; cin>>n>>q;
    vector<PersistentUnionfind> U(q+1);
    for (int i = 0; i < q; i++) {
        int t; cin>>t;
        if (t == 0) {
            int k,u,v; cin>>k>>u>>v;
            U[i+1] = U[k+1].merge(u,v);
        } else {
            int k,u,v; cin>>k>>u>>v;
            cout << U[k+1].same(u,v) << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	conchon_filliatre_tle_00	AC	445 ms	101 MB
g++	conchon_filliatre_tle_01	AC	462 ms	101 MB
g++	example_00	AC	6 ms	3 MB
g++	hand_00	AC	6 ms	3 MB
g++	max_random_00	AC	1223 ms	322 MB
g++	max_random_01	AC	1037 ms	323 MB
g++	max_random_02	AC	1075 ms	325 MB
g++	max_random_03	AC	1067 ms	323 MB
g++	max_random_04	AC	985 ms	323 MB
g++	random_00	AC	720 ms	242 MB
g++	random_01	AC	888 ms	236 MB
g++	random_02	AC	611 ms	195 MB
g++	random_03	AC	102 ms	36 MB
g++	random_04	AC	376 ms	111 MB
clang++	conchon_filliatre_tle_00	AC	452 ms	101 MB
clang++	conchon_filliatre_tle_01	AC	459 ms	101 MB
clang++	example_00	AC	6 ms	3 MB
clang++	hand_00	AC	5 ms	3 MB
clang++	max_random_00	AC	1067 ms	322 MB
clang++	max_random_01	AC	1124 ms	323 MB
clang++	max_random_02	AC	1131 ms	324 MB
clang++	max_random_03	AC	1158 ms	323 MB
clang++	max_random_04	AC	1050 ms	323 MB
clang++	random_00	AC	798 ms	242 MB
clang++	random_01	AC	831 ms	236 MB
clang++	random_02	AC	567 ms	195 MB
clang++	random_03	AC	125 ms	36 MB
clang++	random_04	AC	363 ms	111 MB

Back to top page