This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind" #include "../../data_structure/persistent_unionfind.hpp" #include <iostream> #include <vector> int main() { int n, q; std::cin >> n >> q; ebi::persistent_unionfind uf(n); std::vector<int> query(q + 1, 0); int time = 0; for (int i = 1; i <= q; i++) { int t, k, u, v; std::cin >> t >> k >> u >> v; k = query[k + 1]; query[i] = k; if (t == 0) { uf.merge(u, v, k); query[i] = ++time; } else { if (uf.same(u, v, k)) { std::cout << "1\n"; } else { std::cout << "0\n"; } } } }
#line 1 "test/data_structure/Persistent_Unionfind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind" #line 2 "data_structure/persistent_unionfind.hpp" #include <cstdint> #include <memory> #include <vector> #line 2 "data_structure/persistent_array.hpp" #include <cassert> #line 7 "data_structure/persistent_array.hpp" /* reference: https://37zigen.com/persistent-array/ */ namespace ebi { template <class T, std::size_t m> struct persistent_array { private: struct Node; using node_ptr = std::shared_ptr<Node>; using size_t = std::size_t; struct Node { T val; std::vector<node_ptr> chr; Node(T val, std::vector<node_ptr> chr = std::vector<node_ptr>(m)) : val(val), chr(chr) {} node_ptr get_chr(int i) { return chr[i]; } void update_chr(int i, node_ptr node) { chr[i] = node; } }; std::vector<node_ptr> root; int now; public: persistent_array(std::size_t n, T val) : now(0) { root.emplace_back(std::make_shared<Node>(val)); for (size_t i = 1; i < n; i++) { node_ptr node = root[0]; size_t ret = i; while (ret > 0) { if (node->chr[ret % m] == nullptr) { node->chr[ret % m] = std::make_shared<Node>(val); } node = node->chr[ret % m]; ret /= m; } if (node == nullptr) { node = std::make_shared<Node>(val); } } } persistent_array(std::vector<T> a) : now(0) { size_t n = a.size(); root.emplace_back(std::make_shared<Node>(a[0])); for (size_t i = 1; i < n; i++) { node_ptr node = root[0]; size_t ret = i; while (ret > 0) { if (node->chr[ret % m] == nullptr) { node->chr[ret % m] = std::make_shared<Node>(a[i]); } node = node->chr[ret % m]; ret /= m; } if (node == nullptr) { node = std::make_shared<Node>(a[i]); } } } T get(size_t i, int time = -1) { assert(time <= now); if (time < 0) time = now; node_ptr node = root[time]; while (i > 0) { node = node->chr[i % m]; i /= m; } return node->val; } void set(size_t i, T val, int time = -1) { if (time < 0) time = now; assert(time <= now); node_ptr p = root[time]; node_ptr node = std::make_shared<Node>(p->val, p->chr); root.emplace_back(node); while (i > 0) { p = p->chr[i % m]; node->chr[i % m] = std::make_shared<Node>(p->val, p->chr); node = node->chr[i % m]; i /= m; } node->val = val; now++; } void add(size_t i, T rhs, int time = -1) { if (time < 0) time = now; assert(time <= now); node_ptr p = root[time]; node_ptr node = std::make_shared<Node>(p->val, p->chr); root.emplace_back(node); while (i > 0) { p = p->chr[i % m]; node->chr[i % m] = std::make_shared<Node>(p->val, p->chr); node = node->chr[i % m]; i /= m; } node->val += rhs; now++; } void update(size_t i, T rhs, int time = -1) { if (time < 0) time = now; assert(time <= now); node_ptr node = root[time]; node_ptr p = root[time]; while (i > 0) { p = p->chr[i % m]; node->chr[i % m] = std::make_shared<Node>(p->val, p->chr); node = node->chr[i % m]; i /= m; } node->val = rhs; } }; } // namespace ebi #line 8 "data_structure/persistent_unionfind.hpp" namespace ebi { struct persistent_unionfind { private: using size_t = std::size_t; persistent_array<int, 64> par; public: persistent_unionfind(size_t n) : par(std::vector<int>(n, -1)) {} int leader(int x, int time = -1) { int val = par.get(x, time); if (val < 0) return x; else return leader(val, time); } bool merge(int x, int y, int time = -1) { x = leader(x, time); y = leader(y, time); if (x == y) { par.set(0, par.get(0)); return false; } int val_x = par.get(x, time); int val_y = par.get(y, time); if (val_x > val_y) std::swap(x, y); par.set(x, val_x + val_y, time); par.update(y, x); return true; } bool same(int x, int y, int time = -1) { return leader(x, time) == leader(y, time); } int size(int x, int time = -1) { return -par.get(leader(x, time)); } }; } // namespace ebi #line 4 "test/data_structure/Persistent_Unionfind.test.cpp" #include <iostream> #line 7 "test/data_structure/Persistent_Unionfind.test.cpp" int main() { int n, q; std::cin >> n >> q; ebi::persistent_unionfind uf(n); std::vector<int> query(q + 1, 0); int time = 0; for (int i = 1; i <= q; i++) { int t, k, u, v; std::cin >> t >> k >> u >> v; k = query[k + 1]; query[i] = k; if (t == 0) { uf.merge(u, v, k); query[i] = ++time; } else { if (uf.same(u, v, k)) { std::cout << "1\n"; } else { std::cout << "0\n"; } } } }