test/ufpotential.test.cpp

• View this file on GitHub
• Last update: 2024-03-03 06:51:22+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B

Depends on

• ポテンシャル付きUnionFind (C++/ds/uf/UFPotential.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B"
#include <iostream>
#include "C++/ds/uf/UFPotential.hpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    UFPotential uf(n);
    while(q--) {
        int t, x, y;
        std::cin >> t >> x >> y;
        if(t) {
            if(uf[x] == uf[y]) {
                std::cout << uf.dist(x, y) << '\n';
            }
            else {
                std::cout << "?\n";
            }
        }
        else {
            int z;
            std::cin >> z;
            uf.unite(x, y, z);
        }
    }
}

#line 1 "test/ufpotential.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_B"
#include <iostream>
#line 2 "C++/ds/uf/UFPotential.hpp"

#include <vector>
struct UFPotential {
private:
    std::vector<int> par;
    std::vector<long long> diff;
public:
    UFPotential(const int n): par(n, -1), diff(n){}
    int root(const int i) {
        if(par[i] < 0) {
            return i;
        }
        const int r = root(par[i]);
        diff[i] += diff[par[i]];
        return par[i] = r;
    }
    long long dist(const int i) {
        root(i);
        return diff[i];
    }
    long long dist(const int x, const int y){ return dist(y) - dist(x); }
    int unite(int x, int y, long long w) {
        w += dist(y, x);
        x = root(x), y = root(y);
        if(x == y) {
            return w == 0 ? 0 : -1;
        }
        if(par[x] > par[y]) {
            std::swap(x, y);
            w = -w;
        }
        par[x] += par[y];
        par[y] = x;
        diff[y] = w;
        return 1;
    }
    int operator[](const int i) noexcept { return root(i); }
};
/**
 * @brief ポテンシャル付きUnionFind
 * @see https://github.com/tatyam-prime/kyopro_library/blob/master/UnionFind.cpp
 */
#line 4 "test/ufpotential.test.cpp"
int main() {
    int n, q;
    std::cin >> n >> q;
    UFPotential uf(n);
    while(q--) {
        int t, x, y;
        std::cin >> t >> x >> y;
        if(t) {
            if(uf[x] == uf[y]) {
                std::cout << uf.dist(x, y) << '\n';
            }
            else {
                std::cout << "?\n";
            }
        }
        else {
            int z;
            std::cin >> z;
            uf.unite(x, y, z);
        }
    }
}

Back to top page