test/yosupo/persistent_unionfind.test.cpp

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

Depends on

• 永続配列 (src/DataStructure/PersistentArray.hpp)
• Union-Find(完全永続) (src/DataStructure/UnionFind_Persistent.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/persistent_unionfind
// competitive-verifier: TLE 1
// competitive-verifier: MLE 1024
#include <iostream>
#include <vector>
#include "src/DataStructure/PersistentArray.hpp"
#include "src/DataStructure/UnionFind_Persistent.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<UnionFind_Persistent> uf(Q + 1);
 uf[0]= UnionFind_Persistent(N);
 for (int i= 1; i <= Q; i++) {
  int t, k, u, v;
  cin >> t >> k >> u >> v;
  k++;
  if (t) {
   cout << uf[k].connected(u, v) << '\n';
  } else {
   uf[i]= uf[k];
   uf[i].unite(u, v);
  }
 }
}

#line 1 "test/yosupo/persistent_unionfind.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/persistent_unionfind
// competitive-verifier: TLE 1
// competitive-verifier: MLE 1024
#include <iostream>
#include <vector>
#line 3 "src/DataStructure/PersistentArray.hpp"
template <class T, size_t M= 8> class PersistentArray {
 struct Node {
  T val;
  Node *ch[M];
 } *root;
 T get(Node *t, size_t k) const { return t ? (k ? get(t->ch[(k - 1) % M], (k - 1) / M) : t->val) : T(); }
 bool is_null(Node *t, size_t k) const { return t ? (k ? is_null(t->ch[(k - 1) % M], (k - 1) / M) : false) : true; }
 template <bool persistent= true> T &at(Node *&t, size_t k) {
  if (!t) t= new Node();
  else if constexpr (persistent) t= new Node(*t);
  return k ? at<persistent>(t->ch[(k - 1) % M], (k - 1) / M) : t->val;
 }
public:
 PersistentArray(): root(nullptr) {}
 PersistentArray(size_t n, T v): root(nullptr) {
  for (size_t i= n; i--;) at<false>(root, i)= v;
 }
 PersistentArray(T *bg, T *ed): root(nullptr) {
  for (size_t i= ed - bg; i--;) at<false>(root, i)= *(bg + i);
 }
 PersistentArray(const std::vector<T> &ar): PersistentArray(ar.data(), ar.data() + ar.size()) {}
 bool is_null(size_t k) const { return is_null(root, k); }
 T get(size_t k) const { return get(root, k); }
 T &at(size_t k) { return at<true>(root, k); }
 T &operator[](size_t k) { return at(k); }
 T operator[](size_t k) const { return get(k); }
};
#line 3 "src/DataStructure/UnionFind_Persistent.hpp"
struct UnionFind_Persistent {
 PersistentArray<int, 64> par;
 UnionFind_Persistent() {}
 UnionFind_Persistent(int n): par(n, -1) {}
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par.get(u) > par.get(v)) std::swap(u, v);
  par[u]+= par.get(v), par[v]= u;
  return true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int leader(int u) const { return par.get(u) < 0 ? u : leader(par.get(u)); }
 int size(int u) const { return -par.get(leader(u)); }
};
#line 8 "test/yosupo/persistent_unionfind.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<UnionFind_Persistent> uf(Q + 1);
 uf[0]= UnionFind_Persistent(N);
 for (int i= 1; i <= Q; i++) {
  int t, k, u, v;
  cin >> t >> k >> u >> v;
  k++;
  if (t) {
   cout << uf[k].connected(u, v) << '\n';
  } else {
   uf[i]= uf[k];
   uf[i].unite(u, v);
  }
 }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	conchon_filliatre_tle_00	AC	295 ms	398 MB
g++-13	conchon_filliatre_tle_01	AC	297 ms	398 MB
g++-13	example_00	AC	5 ms	4 MB
g++-13	hand_00	AC	5 ms	4 MB
g++-13	max_random_00	AC	400 ms	517 MB
g++-13	max_random_01	AC	405 ms	518 MB
g++-13	max_random_02	AC	404 ms	519 MB
g++-13	max_random_03	AC	400 ms	519 MB
g++-13	max_random_04	AC	403 ms	517 MB
g++-13	random_00	AC	295 ms	373 MB
g++-13	random_01	AC	295 ms	388 MB
g++-13	random_02	AC	184 ms	222 MB
g++-13	random_03	AC	92 ms	143 MB
g++-13	random_04	AC	76 ms	70 MB
clang++-18	conchon_filliatre_tle_00	AC	301 ms	398 MB
clang++-18	conchon_filliatre_tle_01	AC	299 ms	398 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	hand_00	AC	4 ms	4 MB
clang++-18	max_random_00	AC	404 ms	517 MB
clang++-18	max_random_01	AC	407 ms	518 MB
clang++-18	max_random_02	AC	408 ms	519 MB
clang++-18	max_random_03	AC	408 ms	519 MB
clang++-18	max_random_04	AC	409 ms	517 MB
clang++-18	random_00	AC	294 ms	373 MB
clang++-18	random_01	AC	298 ms	388 MB
clang++-18	random_02	AC	187 ms	222 MB
clang++-18	random_03	AC	92 ms	143 MB
clang++-18	random_04	AC	76 ms	70 MB

Back to top page