This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind" #include "DataStructure/PersistentUnionFind.hpp" #include <cstdio> #include <vector> int main() { int N, Q; scanf("%d %d", &N, &Q); using PUF = PersistentUnionFind<6>; std::vector<PUF> hist(Q + 1); for (int i = 0; i < Q; ++i) { int t, k, u, v; scanf("%d %d %d %d", &t, &k, &u, &v); ++k; if (t == 0) hist[i + 1] = (hist[k].unite(u, v)); else printf("%d\n", hist[k].issame(u, v)); } }
#line 1 "Test/PersistentUnionFind.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind" #line 1 "DataStructure/PersistentUnionFind.hpp" #line 1 "DataStructure/PersistentArray.hpp" #include <memory> #include <utility> /** * @brief https://tkmst201.github.io/Library/DataStructure/PersistentArray.hpp */ template<typename T, int M> struct PersistentArray { static_assert(M > 1); using value_type = T; using const_reference = const value_type &; using size_type = std::size_t; private: struct Node; using sptr_type = std::shared_ptr<Node>; using node_ptr = Node *; using const_ptr = const Node *; struct Node { sptr_type childs[M]; value_type val; Node(const_reference val) : val(val) {} }; private: sptr_type root; value_type def_val; private: PersistentArray(const sptr_type & root, const_reference def_val) : root(root), def_val(def_val) {} public: explicit PersistentArray(const_reference def_val = 0) : root(nullptr), def_val(def_val) {} PersistentArray set(size_type k, const_reference x) const { const_ptr node = root.get(); sptr_type new_root = std::make_shared<Node>(k == 0 ? x : (node ? node->val : def_val)); node_ptr new_node = new_root.get(); for (; k > 0; k /= M) { const size_type m = k % M; if (node) { for (size_type i = 0; i < M; ++i) if (i != m) new_node->childs[i] = node->childs[i]; new_node->childs[m] = std::make_shared<Node>(k < M ? x : (node->childs[m] ? node->childs[m]->val : def_val)); node = node->childs[m].get(); } else new_node->childs[m] = std::make_shared<Node>(k < M ? x : def_val); new_node = new_node->childs[m].get(); } if (node) for (size_type i = 0; i < M; ++i) new_node->childs[i] = node->childs[i]; return {std::move(new_root), def_val}; } void destructive_set(size_type k, const_reference x) { if (!root) root = std::make_shared<Node>(k == 0 ? x : def_val); node_ptr node = root.get(); for (; k >= M; k /= M) { const size_type m = k % M; if (!node->childs[m]) node->childs[m] = std::make_shared<Node>(def_val); node = node->childs[m].get(); } if (node->childs[k]) node->childs[k]->val = x; else node->childs[k] = std::make_shared<Node>(x); } const_reference get(size_type k) const noexcept { const_ptr node = root.get(); while (k > 0 && node) { node = node->childs[k % M].get(); k /= M; } return k == 0 && node ? node->val : def_val; } }; #line 5 "DataStructure/PersistentUnionFind.hpp" #include <cstdint> #line 8 "DataStructure/PersistentUnionFind.hpp" /** * @brief https://tkmst201.github.io/Library/DataStructure/PersistentUnionFind.hpp */ template<int M> struct PersistentUnionFind { static_assert(M > 1); using size_type = std::size_t; private: using parray_type = PersistentArray<int, M>; parray_type dat; public: PersistentUnionFind() : dat(-1) {} private: PersistentUnionFind(const parray_type & dat) : dat(dat) {} public: size_type find(size_type x) const noexcept { return find_sub(x).first; } size_type size(size_type x) const noexcept { return find_sub(x).second; } private: std::pair<size_type, int> find_sub(size_type x) const noexcept { int d; for (d = dat.get(x); d >= 0; d = dat.get(x)) x = d; return {x, -d}; } public: PersistentUnionFind unite(size_type x, size_type y) const { if (x == y) return *this; auto px = find_sub(x), py = find_sub(y); if (px.first == py.first) return *this; if (px.second > py.second) std::swap(px, py); return dat.set(px.first, py.first).set(py.first, -(px.second + py.second)); } void destructive_unite(size_type x, size_type y) { if (x == y) return; auto px = find_sub(x), py = find_sub(y); if (px.first == py.first) return; if (px.second > py.second) std::swap(px, py); dat.destructive_set(px.first, py.first); dat.destructive_set(py.first, -(px.second + py.second)); } bool issame(size_type x, size_type y) const noexcept { return x == y ? true : find(x) == find(y); } }; #line 4 "Test/PersistentUnionFind.test.cpp" #include <cstdio> #include <vector> int main() { int N, Q; scanf("%d %d", &N, &Q); using PUF = PersistentUnionFind<6>; std::vector<PUF> hist(Q + 1); for (int i = 0; i < Q; ++i) { int t, k, u, v; scanf("%d %d %d %d", &t, &k, &u, &v); ++k; if (t == 0) hist[i + 1] = (hist[k].unite(u, v)); else printf("%d\n", hist[k].issame(u, v)); } }