cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/datastructure/union_find/persistent_union_find/persistent_unionfind.test.cpp

Depends on

Code

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

#include <iostream>

#include "library/datastructure/union_find/persistent_union_find.hpp"

using suisen::PersistentUnionFind;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    PersistentUnionFind::init_pool(1400000);

    std::vector<PersistentUnionFind> ufs;
    ufs.push_back(PersistentUnionFind(n));

    for (int time = 1; time <= q; ++time) {
        int query_type, k, u, v;
        std::cin >> query_type >> k >> u >> v;
        ++k;
        if (query_type == 0) {
            ufs.push_back(ufs[k].merge(u, v).first);
        } else {
            ufs.push_back(ufs[time - 1]);
            std::cout << ufs[k].same(u, v) << '\n';
        }
    }

    return 0;
}
#line 1 "test/src/datastructure/union_find/persistent_union_find/persistent_unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#include <iostream>

#line 1 "library/datastructure/union_find/persistent_union_find.hpp"



#include <algorithm>
#include <utility>

#line 1 "library/datastructure/persistent_array.hpp"



#line 1 "library/util/object_pool.hpp"



#include <deque>
#include <vector>

namespace suisen {
    template <typename T, bool auto_extend = false>
    struct ObjectPool {
        using value_type = T;
        using value_pointer_type = T*;

        template <typename U>
        using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>;

        container_type<value_type> pool;
        container_type<value_pointer_type> stock;
        decltype(stock.begin()) it;

        ObjectPool() : ObjectPool(0) {}
        ObjectPool(int siz) : pool(siz), stock(siz) {
            clear();
        }

        int capacity() const { return pool.size(); }
        int size() const { return it - stock.begin(); }

        value_pointer_type alloc() {
            if constexpr (auto_extend) ensure();
            return *it++;
        }

        void free(value_pointer_type t) {
            *--it = t;
        }

        void clear() {
            int siz = pool.size();
            it = stock.begin();
            for (int i = 0; i < siz; i++) stock[i] = &pool[i];
        }

        void ensure() {
            if (it != stock.end()) return;
            int siz = stock.size();
            for (int i = siz; i <= siz * 2; ++i) {
                stock.push_back(&pool.emplace_back());
            }
            it = stock.begin() + siz;
        }
    };
} // namespace suisen


#line 6 "library/datastructure/persistent_array.hpp"

namespace suisen {
    template <typename T, int lg_ary = 4>
    struct PersistentArray {
        struct Node;
        using node_type = Node;
        using node_pointer_type = node_type*;
        using value_type = T;
        using pool_type = ObjectPool<node_type>;
        struct Node {
            static inline pool_type pool{};
            static constexpr int mask = (1 << lg_ary) - 1;

            node_pointer_type _ch[1 << lg_ary]{};
            value_type _val;
            Node(const value_type& val = value_type{}) : _val(val) {}

            static node_pointer_type clone(node_pointer_type node) {
                return &(*pool.alloc() = *node);
            }
            static node_pointer_type new_node(const value_type& val) {
                return &(*pool.alloc() = node_type(val));
            }
            static value_type& get(node_pointer_type node, int id) {
                for (; id; --id >>= lg_ary) node = node->_ch[id & mask];
                return node->_val;
            }
            static node_pointer_type set(node_pointer_type node, int id, const value_type& val) {
                node_pointer_type res = clone(node), cur = res;
                for (; id; --id >>= lg_ary) cur = cur->_ch[id & mask] = clone(cur->_ch[id & mask]);
                cur->_val = val;
                return res;
            }
            static value_type mut_set(node_pointer_type node, int id, const value_type& val) {
                return std::exchange(get(node, id), val);
            }
            static node_pointer_type build(const std::vector<value_type>& init) {
                const int n = init.size();
                if (n == 0) return nullptr;
                auto dfs = [&](auto dfs, node_pointer_type cur, int id, int p) -> void {
                    int np = p << lg_ary, nid = id + p;
                    for (int d = 1; d < 1 << lg_ary; ++d, nid += p) {
                        if (nid < n) dfs(dfs, cur->_ch[d] = new_node(init[nid]), nid, np);
                        else return;
                    }
                    if (nid < n) dfs(dfs, cur->_ch[0] = new_node(init[nid]), nid, np);
                };
                node_pointer_type root = new_node(init[0]);
                dfs(dfs, root, 0, 1);
                return root;
            }
            static std::vector<value_type> dump(node_pointer_type node) {
                if (not node) return {};
                std::vector<value_type> res;
                auto dfs = [&](auto dfs, node_pointer_type cur, int id, int p) -> void {
                    if (int(res.size()) <= id) res.resize(id + 1);
                    res[id] = node->_val;
                    int np = p << lg_ary, nid = id + p;
                    for (int d = 1; d < 1 << lg_ary; ++d, nid += p) {
                        if (cur->_ch[d]) dfs(dfs, cur->_ch[d], nid, np);
                        else return;
                    }
                    if (cur->_ch[0]) dfs(dfs, cur->_ch[0], nid, np);
                };
                dfs(dfs, node, 0, 1);
                return res;
            }
        };

        static void init_pool(int capacity) {
            node_type::pool = pool_type(capacity);
        }

        PersistentArray() = default;
        explicit PersistentArray(int n, const value_type& val = value_type{}) : PersistentArray(std::vector<value_type>(n, val)) {}
        PersistentArray(const std::vector<value_type>& init) : _n(init.size()), _root(node_type::build(init)) {}

        int size() const {
            return _n;
        }
        const value_type& get(int id) {
            return node_type::get(_root, id);
        }
        PersistentArray set(int id, const value_type& new_val) {
            return PersistentArray{ _n, node_type::set(_root, id, new_val) };
        }
        value_type mut_set(int id, const value_type& new_val) {
            return node_type::mut_set(_root, id, new_val);
        }
        PersistentArray clone() {
            if (not _root) return PersistentArray { _n, _root };
            return PersistentArray{ _n, node_type::clone(_root) };
        }
        std::vector<value_type> dump() {
            return node_type::dump(_root);
        }
    private:
        int _n;
        node_pointer_type _root;
        explicit PersistentArray(int n, node_pointer_type root) : _n(n), _root(root) {}
    };
} // namespace suisen


#line 8 "library/datastructure/union_find/persistent_union_find.hpp"

namespace suisen {
    struct PersistentUnionFind {
        using array_type = PersistentArray<int, 4>;

        PersistentUnionFind() = default;
        explicit PersistentUnionFind(int n) : _n(n), _dat(_n, -1) {}

        static void init_pool(int capacity) {
            array_type::init_pool(capacity);
        }

        // Get the root of `x`. equivalent to `operator[](x)`
        int root(int x) {
            static std::vector<int> buf;
            while (true) {
                if (int r = _dat.get(x); r >= 0) buf.push_back(std::exchange(x, r));
                else break;
            }
            while (buf.size()) _dat.mut_set(buf.back(), x), buf.pop_back();
            return x;
        }
        // Get the root of `x`. euivalent to `root(x)`
        int operator[](int x) {
            return root(x);
        }
        // Merge two vertices `x` and `y`.
        std::pair<PersistentUnionFind, bool> merge(int x, int y) {
            x = root(x), y = root(y);
            if (x == y) return { *this, false };
            int vx = _dat.get(x), vy = _dat.get(y);
            if (vx > vy) std::swap(x, y), std::swap(vx, vy);
            array_type new_dat = _dat;
            new_dat = new_dat.set(x, vx + vy);
            new_dat = new_dat.set(y, x);
            return { PersistentUnionFind(new_dat), true };
        }
        // Check if `x` and `y` belongs to the same connected component.
        bool same(int x, int y) {
            return root(x) == root(y);
        }
        // Get the size of connected componet to which `x` belongs.
        int size(int x) {
            return -_dat.get(root(x));
        }
        // Get all of connected components.
        std::vector<std::vector<int>> groups() {
            std::vector<std::vector<int>> res(_n);
            for (int i = 0; i < _n; ++i) res[root(i)].push_back(i);
            res.erase(std::remove_if(res.begin(), res.end(), [](const auto& g) { return g.empty(); }), res.end());
            return res;
        }
        std::vector<int> dump() {
            return _dat.dump();
        }
    protected:
        int _n;
        array_type _dat;

        explicit PersistentUnionFind(array_type dat) : _n(dat.size()), _dat(dat) {}
    };
} // namespace suisen



#line 6 "test/src/datastructure/union_find/persistent_union_find/persistent_unionfind.test.cpp"

using suisen::PersistentUnionFind;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    PersistentUnionFind::init_pool(1400000);

    std::vector<PersistentUnionFind> ufs;
    ufs.push_back(PersistentUnionFind(n));

    for (int time = 1; time <= q; ++time) {
        int query_type, k, u, v;
        std::cin >> query_type >> k >> u >> v;
        ++k;
        if (query_type == 0) {
            ufs.push_back(ufs[k].merge(u, v).first);
        } else {
            ufs.push_back(ufs[time - 1]);
            std::cout << ufs[k].same(u, v) << '\n';
        }
    }

    return 0;
}
Back to top page