test/unionfind_with_potential.test.cpp

• View this file on GitHub
• Last update: 2025-05-28 17:58:43+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind_with_potential

Depends on

• Union Find With Potential (data_structure/unionfind_with_potential.hpp)
• Modint (math/modint.hpp)

Code

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

#include <data_structure/unionfind_with_potential.hpp>  // for WeightedUnionfind
#include <fastio/base.hpp>                              // for FASTIO, cout, cin
#include <fastio/char/write.hpp>                        // for operator<<
#include <fastio/modint/write.hpp>                      // for operator<<
#include <fastio/signed/read.hpp>                       // for operator>>
#include <fastio/signed/write.hpp>                      // for operator<<
#include <math/modint.hpp>                              // for ModInt
#include <templates/macro/abbrev/endl.hpp>              // for endl
#include <templates/macro/abbrev/ll.hpp>                // for ll
#include <templates/macro/mod.hpp>                      // for MOD1
#include <templates/rep.hpp>                            // for rep
#include <templates/template.hpp>
#include <version>  // for std

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    UnionFindWithPotential<ll> uf(n);
    using mint = Modint<MOD1>;
    rep(_, q) {
        int t;
        cin >> t;
        if (t) {
            ll u, v;
            cin >> u >> v;
            if (uf.same(u, v)) {
                ll it = uf.weight(v, u);
                if (it < 0) {
                    it -= (it / MOD1 - 1) * MOD1;
                }
                cout << mint{it} << endl;
            } else {
                cout << -1 << endl;
            }
        } else {
            ll u, v, x;
            cin >> u >> v >> x;
            if (!uf.same(u, v)) {
                uf.merge(v, u, x);
                cout << 1 << endl;
            } else {
                ll it = uf.weight(v, u);
                if (it < 0) {
                    it -= (it / MOD1 - 1) * MOD1;
                }
                it %= MOD1;
                if (x < 0) {
                    x -= (x / MOD1 - 1) * MOD1;
                }
                if (it == x) {
                    cout << 1 << endl;
                } else {
                    cout << 0 << endl;
                }
            }
        }
    }
}

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

#include <data_structure/unionfind_with_potential.hpp>  // for WeightedUnionfind
#include <fastio/base.hpp>                              // for FASTIO, cout, cin
#include <fastio/char/write.hpp>                        // for operator<<
#include <fastio/modint/write.hpp>                      // for operator<<
#include <fastio/signed/read.hpp>                       // for operator>>
#include <fastio/signed/write.hpp>                      // for operator<<
#include <math/modint.hpp>                              // for ModInt
#include <templates/macro/abbrev/endl.hpp>              // for endl
#include <templates/macro/abbrev/ll.hpp>                // for ll
#include <templates/macro/mod.hpp>                      // for MOD1
#include <templates/rep.hpp>                            // for rep
#include <templates/template.hpp>
#include <version>  // for std

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    UnionFindWithPotential<ll> uf(n);
    using mint = Modint<MOD1>;
    rep(_, q) {
        int t;
        cin >> t;
        if (t) {
            ll u, v;
            cin >> u >> v;
            if (uf.same(u, v)) {
                ll it = uf.weight(v, u);
                if (it < 0) {
                    it -= (it / MOD1 - 1) * MOD1;
                }
                cout << mint{it} << endl;
            } else {
                cout << -1 << endl;
            }
        } else {
            ll u, v, x;
            cin >> u >> v >> x;
            if (!uf.same(u, v)) {
                uf.merge(v, u, x);
                cout << 1 << endl;
            } else {
                ll it = uf.weight(v, u);
                if (it < 0) {
                    it -= (it / MOD1 - 1) * MOD1;
                }
                it %= MOD1;
                if (x < 0) {
                    x -= (x / MOD1 - 1) * MOD1;
                }
                if (it == x) {
                    cout << 1 << endl;
                } else {
                    cout << 0 << endl;
                }
            }
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	24 ms	4 MB
g++	max_random_00	AC	25 ms	11 MB
g++	max_random_01	AC	25 ms	11 MB
g++	max_random_02	AC	29 ms	10 MB
g++	path_00	AC	20 ms	13 MB
g++	path_01	AC	22 ms	13 MB
g++	path_02	AC	22 ms	13 MB
g++	path_03	AC	23 ms	13 MB
g++	random_00	AC	20 ms	10 MB
g++	random_01	AC	18 ms	10 MB
g++	random_02	AC	17 ms	9 MB
g++	random_03	AC	8 ms	6 MB
g++	random_04	AC	16 ms	6 MB
g++	random_05	AC	20 ms	9 MB
g++	random_06	AC	15 ms	10 MB
g++	random_07	AC	6 ms	5 MB
g++	random_08	AC	11 ms	5 MB
g++	random_09	AC	26 ms	11 MB

Back to top page