test/persistent_unionfind.test.cpp

• View this file on GitHub
• Last update: 2025-06-22 16:22:13+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_unionfind

Depends on

• Persistent Array (data_structure/persistent_array.hpp)
• Persistent Union Find (data_structure/persistent_unionfind.hpp)

Code

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

#include <data_structure/persistent_unionfind.hpp>  // for PersistentUnionfind
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <vector>  // for vector

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    PersistentUnionFind uf(n);
    vector<int> a(q);
    rep(i, q) {
        int t, x, u, v;
        cin >> t >> x >> u >> v;
        ++x;
        if (t == 0) {
            a[i] = uf.merge(u, v, x == 0 ? 0 : a[x - 1]);
        } else {
            cout << static_cast<int>(uf.same(u, v, x == 0 ? 0 : a[x - 1])) << endl;
        }
    }
}

#line 1 "test/persistent_unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind"

#include <data_structure/persistent_unionfind.hpp>  // for PersistentUnionfind
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <vector>  // for vector

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    PersistentUnionFind uf(n);
    vector<int> a(q);
    rep(i, q) {
        int t, x, u, v;
        cin >> t >> x >> u >> v;
        ++x;
        if (t == 0) {
            a[i] = uf.merge(u, v, x == 0 ? 0 : a[x - 1]);
        } else {
            cout << static_cast<int>(uf.same(u, v, x == 0 ? 0 : a[x - 1])) << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	conchon_filliatre_tle_00	AC	850 ms	427 MB
g++	conchon_filliatre_tle_01	AC	801 ms	427 MB
g++	example_00	AC	5 ms	4 MB
g++	hand_00	AC	5 ms	4 MB
g++	max_random_00	AC	1305 ms	426 MB
g++	max_random_01	AC	1264 ms	427 MB
g++	max_random_02	AC	1272 ms	428 MB
g++	max_random_03	AC	1279 ms	428 MB
g++	max_random_04	AC	1260 ms	426 MB
g++	random_00	AC	892 ms	316 MB
g++	random_01	AC	940 ms	325 MB
g++	random_02	AC	414 ms	158 MB
g++	random_03	AC	230 ms	115 MB
g++	random_04	AC	133 ms	54 MB

Back to top page