test/potentialized_unionfind1.test.cpp

• View this file on GitHub
• Last update: 2022-12-05 12:46:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B

Depends on

• potentialized_unionfind (ポテンシャル付きUnion Find木) (src/dataStructure/potentialized_unionfind.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"

#include "../src/dataStructure/potentialized_unionfind.hpp"

#include <iostream>

int main() {
    int n, q;
    std::cin >> n >> q;
    zawa::potentialized_unionfind<int> uf(n);
    for (int _ = 0 ; _ < q ; _++) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int x, y, z;
            std::cin >> x >> y >> z;
            uf.merge(x, y, z);
        }
        if (t == 1) {
            int x, y;
            std::cin >> x >> y;
            if (uf.same(x, y)) {
                std::cout << uf.diff(y, x) << std::endl;
            }
            else {
                std::cout << '?' << std::endl;
            }
        }
    }
}

#line 1 "test/potentialized_unionfind1.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"

#line 2 "src/dataStructure/potentialized_unionfind.hpp"

#include <vector>
#include <utility>

namespace zawa {

template <class cost_type>
class potentialized_unionfind {
private:
    std::vector<int> parents;
    std::vector<int> sizes;
    std::vector<cost_type> weights;

    int rooting(int x) {
        if (parents[x] == x) {
            return x;
        }
        else {
            int root = rooting(parents[x]);
            weights[x] += weights[parents[x]];
            return parents[x] = root;
        }
    }

    cost_type get_weight(int x) {
        rooting(x);
        return weights[x];
    }

public:

    potentialized_unionfind(std::size_t n) : parents(n, 0), sizes(n, 1), weights(n) {
        for (std::size_t i = 0 ; i < n ; i++) {
            parents[i] = i;
        }
    }

    int leader(int x) {
        return rooting(x);
    }

    bool same(int x, int y) {
        return rooting(x) == rooting(y);
    }

    bool merge(int x, int y, cost_type w) {
        w += get_weight(x);
        w -= get_weight(y);
        int rx = rooting(x), ry = rooting(y);
        if (rx == ry) {
            return false;
        }
        if (sizes[rx] < sizes[ry]) {
            std::swap(rx, ry);
            w *= -1;
        }
        sizes[rx] += sizes[ry];
        parents[ry] = rx;
        weights[ry] = w;
        return true;
    }

    cost_type diff(int y, int x) {
        return get_weight(y) - get_weight(x);
    }
};

} // namespace zawa
#line 4 "test/potentialized_unionfind1.test.cpp"

#include <iostream>

int main() {
    int n, q;
    std::cin >> n >> q;
    zawa::potentialized_unionfind<int> uf(n);
    for (int _ = 0 ; _ < q ; _++) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int x, y, z;
            std::cin >> x >> y >> z;
            uf.merge(x, y, z);
        }
        if (t == 1) {
            int x, y;
            std::cin >> x >> y;
            if (uf.same(x, y)) {
                std::cout << uf.diff(y, x) << std::endl;
            }
            else {
                std::cout << '?' << std::endl;
            }
        }
    }
}

Back to top page