test/aoj/DSL_1_B.test.cpp

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

Depends on

• Weighted Union Find (data-structure/unionfind/weighted_union_find.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B"

#include "../../data-structure/unionfind/weighted_union_find.hpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    WeightedUnionFind<int> wuf(n);
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 0) {
            int x, y, z;
            cin >> x >> y >> z;
            wuf.unite(x, y, z);
        } else {
            int x, y;
            cin >> x >> y;
            if (wuf.same(x, y)) cout << wuf.diff(x, y) << "\n";
            else cout << "?\n";
        }
    }
}

#line 1 "test/aoj/DSL_1_B.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B"

#line 2 "data-structure/unionfind/weighted_union_find.hpp"
#include <algorithm>
#include <vector>

template <typename T>
class WeightedUnionFind {
   public:
    WeightedUnionFind() = default;
    explicit WeightedUnionFind(int n) : data(n, -1), ws(n) {}

    int find(int x) {
        if (data[x] < 0) return x;
        int r = find(data[x]);
        ws[x] += ws[data[x]];
        return data[x] = r;
    }

    T weight(int x) {
        find(x);
        return ws[x];
    }

    bool unite(int x, int y, T w) {
        w += weight(x);
        w -= weight(y);
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) {
            std::swap(x, y);
            w = -w;
        }
        data[x] += data[y];
        data[y] = x;
        ws[y] = w;
        return true;
    }

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

    T diff(int x, int y) { return weight(y) - weight(x); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
    std::vector<T> ws;
};
#line 4 "test/aoj/DSL_1_B.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    WeightedUnionFind<int> wuf(n);
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 0) {
            int x, y, z;
            cin >> x >> y >> z;
            wuf.unite(x, y, z);
        } else {
            int x, y;
            cin >> x >> y;
            if (wuf.same(x, y)) cout << wuf.diff(x, y) << "\n";
            else cout << "?\n";
        }
    }
}

Back to top page