verify/aizu_online_judge/dsl/weighted_union_find_trees.test.cpp

View this file on GitHub
Last update: 2024-11-09 01:34:39+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"
#include "../../../src/template/template.hpp"
#include "../../../src/data_structure/weighted_union_find.hpp"
int main(void) {
    int n, q;
    cin >> n >> q;
    WeightedUnionFind<int> uf(n);
    while(q--) {
        int t;
        cin >> t;
        if(t == 0) {
            int x, y, z;
            cin >> x >> y >> z;
            uf.merge(y, x, z);
        } else {
            int x, y;
            cin >> x >> y;
            if(uf.same(x, y)) {
                cout << uf.diff(y, x) << '\n';
            } else {
                cout << '?' << '\n';
            }
        }
    }
}

#line 1 "verify/aizu_online_judge/dsl/weighted_union_find_trees.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/weighted_union_find.hpp"
template <typename T>
struct WeightedUnionFind {
    WeightedUnionFind(const int N)
        : n(N), data(N, -1), ws(N, T()) {}
    bool merge(const int a, const int b, T w) {
        assert(0 <= a and a < n);
        assert(0 <= b and b < n);
        w += weight(b) - weight(a);
        int x = leader(a), y = leader(b);
        if(x == y) return w == T();
        if(-data[x] > -data[y]) swap(x, y), w = -w;
        data[y] += data[x];
        data[x] = y;
        ws[x] = w;
        return true;
    }
    bool same(const int a, const int b) {
        assert(0 <= a and a < n);
        assert(0 <= b and b < n);
        return leader(a) == leader(b);
    }
    int leader(const int a) {
        assert(0 <= a and a < n);
        if(data[a] < 0) return a;
        const int r = leader(data[a]);
        ws[a] += ws[data[a]];
        return data[a] = r;
    }
    int size(const int a) {
        assert(0 <= a and a < n);
        return -data[leader(a)];
    }
    T weight(const int a) {
        assert(0 <= a and a < n);
        leader(a);
        return ws[a];
    }
    T diff(const int a, const int b) {
        assert(0 <= a and a < n);
        assert(0 <= b and b < n);
        return weight(a) - weight(b);
    }

   private:
    int n;
    vector<int> data;
    vector<T> ws;
};
#line 4 "verify/aizu_online_judge/dsl/weighted_union_find_trees.test.cpp"
int main(void) {
    int n, q;
    cin >> n >> q;
    WeightedUnionFind<int> uf(n);
    while(q--) {
        int t;
        cin >> t;
        if(t == 0) {
            int x, y, z;
            cin >> x >> y >> z;
            uf.merge(y, x, z);
        } else {
            int x, y;
            cin >> x >> y;
            if(uf.same(x, y)) {
                cout << uf.diff(y, x) << '\n';
            } else {
                cout << '?' << '\n';
            }
        }
    }
}