test/library_checker/data_structure/persistent_unionfind_1.test.cpp

View this file on GitHub
Last update: 2024-11-18 04:07:23+09:00
Problem: https://judge.yosupo.jp/problem/persistent_unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include <vector>

#include "../../../lib/data_structure/persistent_union_find.hpp"

using namespace std;

using pa = PersistentArray<int>::Node*;

int main(){
    int n, q; cin >> n >> q;
    PersistentUnionFindv2 tree;
    vector<pa> p(q + 1);
    p[0] = tree.init(n);
    int nxt = 1;
    while(q--){
        int t, k, u, v; cin >> t >> k >> u >> v;
        k++;
        if(t == 0){
            p[nxt] = tree.unite(u, v, p[k]).second;
        }else{
            cout << (int) tree.same(u, v, p[k]) << "\n";
        }
        nxt++;
    }
}

#line 1 "test/library_checker/data_structure/persistent_unionfind_1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"
#include <iostream>
#include <vector>

#line 2 "lib/data_structure/persistent_union_find.hpp"

/**
 * @brief Persistent Union Find (永続 UnionFind)
 */

#line 2 "lib/data_structure/persistent_array.hpp"

/**
 * @brief Persistent Array (永続配列)
 */

#include <cstring>

template<typename T>
struct PersistentArray{
    struct Node{
        T data;
        Node *ch[20] = {};
    };
    Node *root = nullptr;

    PersistentArray() {}

    Node *get_root(){
        return root;
    }

    void destructive_set(const int i, const T &val, Node *&t){
        if(!t) t = new Node();
        if(i == 0){
            t->data = val;
        } else{
            destructive_set(i / 20, val, t->ch[i % 20]);
        }
    }

    Node *set(const int i, const T &val, Node *&t){
        Node *res = new Node();
        if(t){
            std::memcpy(res->ch, t->ch, sizeof(t->ch));
            res->data = t->data;
        }
        if(i == 0){
            res->data = val;
        } else{
            res->ch[i % 20] = set(i / 20, val, res->ch[i % 20]);
        }
        return res;
    }

    T get(const int i, Node *t){
        if(!t) return T();
        if(i == 0){
            return t->data;
        } else{
            return get(i / 20, t->ch[i % 20]);
        }
    }
};
#line 8 "lib/data_structure/persistent_union_find.hpp"

struct PersistentUnionFind{
    PersistentArray<int> data;
    using node = PersistentArray<int>::Node *;

    PersistentUnionFind() {}

    node init(const int n){
        node res = data.get_root();
        for(int i = 0; i < n; ++i){
            data.destructive_set(i, -1, res);
        }
        return res;
    }

    std::pair<bool, node> unite(const int x, const int y, node t){
        int rx = root(x, t), ry = root(y, t);
        if(rx == ry) return {false, t};

        if(data.get(ry, t) < data.get(rx, t)) std::swap(rx, ry);

        node n = data.set(rx, data.get(rx, t) + data.get(ry, t), t);
        node res = data.set(ry, rx, n);
        return {true, res};
    }

    int root(const int x, node t){
        if(data.get(x, t) < 0){
            return x;
        }
        int res = root(data.get(x, t), t);
        return res;
    }

    inline bool same(const int x, const int y, node t){
        return root(x, t) == root(y, t);
    }

    inline int size(const int x, node t){
        return -data.get(root(x, t), t);
    }
};

struct PersistentUnionFindv2{
    int n;
    PersistentArray<int> data;
    using node = PersistentArray<int>::Node *;

    PersistentUnionFindv2() {}

    node init(const int &_n){
        n = _n;
        node res = data.get_root();
        for(int i = 0; i < n; ++i){
            data.destructive_set(i, -1, res);
            data.destructive_set(i + n, 0, res);
        }
        return res;
    }

    std::pair<bool, node> unite(const int x, const int y, node t){
        int rx = root(x, t), ry = root(y, t);
        if(rx == ry){
            node res = data.set(rx + n, edge(rx, t) + 1, t);
            return {false, res};
        }

        if(data.get(ry, t) < data.get(rx, t)) std::swap(rx, ry);

        node res = data.set(rx, data.get(rx, t) + data.get(ry, t), t);
        res = data.set(ry, rx, res);
        res = data.set(rx + n, data.get(rx + n, t) + data.get(ry + n, t) + 1, res);
        return {true, res};
    }

    int root(const int x, node t){
        if(data.get(x, t) < 0){
            return x;
        }
        int res = root(data.get(x, t), t);
        return res;
    }

    inline bool same(const int x, const int y, node t){
        return root(x, t) == root(y, t);
    }

    inline int size(const int x, node t){
        return -data.get(root(x, t), t);
    }

    inline int edge(const int x, node t){
        return data.get(root(x, t) + n, t);
    }
};
#line 6 "test/library_checker/data_structure/persistent_unionfind_1.test.cpp"

using namespace std;

using pa = PersistentArray<int>::Node*;

int main(){
    int n, q; cin >> n >> q;
    PersistentUnionFindv2 tree;
    vector<pa> p(q + 1);
    p[0] = tree.init(n);
    int nxt = 1;
    while(q--){
        int t, k, u, v; cin >> t >> k >> u >> v;
        k++;
        if(t == 0){
            p[nxt] = tree.unite(u, v, p[k]).second;
        }else{
            cout << (int) tree.same(u, v, p[k]) << "\n";
        }
        nxt++;
    }
}