test/aoj/DSL1B.test.cpp

• View this file on GitHub
• Last update: 2022-09-01 14:18:35+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

Depends on

• union_find/weighted_union_find.hpp

Code

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

// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#include "../../union_find/weighted_union_find.hpp"

using namespace std;
using llong = long long;

struct A {
    using T = llong;
    using value_type = T;

    static inline T identity() {
        return 0;
    };

    static inline T operation(T x, T y) {
        return x + y;
    };

    static inline T inverse(T x) {
        return -x;
    };
};

llong n, q;
llong com, x, y, w;

int main() {
    cin >> n >> q;
    WeightedUnionFind<A> uf(n);

    while (q--) {
        cin >> com;

        if (com == 0) {
            cin >> x >> y >> w;
            uf.unite(x, y, w);
        } else {
            cin >> x >> y;

            if (uf.same(x, y)) {
                cout << uf.diff(x, y) << '\n';
            } else {
                cout << "?\n";
            }
        }
    }

    return 0;
};

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

// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#line 1 "union_find/weighted_union_find.hpp"


#line 4 "union_find/weighted_union_find.hpp"

//===
template <class Abel>
struct WeightedUnionFind {
    using T = typename Abel::value_type;

    std::vector<int>
        parent;  // [i] = i-th node's parent. if [i] < 0, i-th node is root.
    std::vector<T> diff_weight;  // distance from parent

    WeightedUnionFind() = default;
    WeightedUnionFind(int nmemb) {
        init(nmemb);
    };

    void init(int nmemb) {
        parent.resize(nmemb, -1);
        diff_weight.resize(nmemb, Abel::identity());
    };

    int root(int x) {
        if (parent[x] < 0) return x;

        int p = root(parent[x]);
        diff_weight[x] =
            Abel::operation(diff_weight[x], diff_weight[parent[x]]);
        parent[x] = p;

        return p;
    };

    // unite x, y; weight(y) - weight(x) = w
    bool unite(int x, int y, T w) {
        T wx = weight(x);
        T wy = weight(y);
        x = root(x);
        y = root(y);

        if (x == y) return false;
        w = Abel::operation(w, wx);
        w = Abel::operation(w, Abel::inverse(wy));
        if (size(x) < size(y)) std::swap(x, y), w = Abel::inverse(w);

        parent[x] += parent[y];
        parent[y] = x;
        diff_weight[y] = w;

        return true;
    };

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

    T weight(int x) {
        root(x);
        return diff_weight[x];
    };

    T diff(int x, int y) {
        return Abel::operation(weight(y), Abel::inverse(weight(x)));
    };

    int size(int x) {
        return -parent[root(x)];
    };
};
//===


#line 19 "test/aoj/DSL1B.test.cpp"

using namespace std;
using llong = long long;

struct A {
    using T = llong;
    using value_type = T;

    static inline T identity() {
        return 0;
    };

    static inline T operation(T x, T y) {
        return x + y;
    };

    static inline T inverse(T x) {
        return -x;
    };
};

llong n, q;
llong com, x, y, w;

int main() {
    cin >> n >> q;
    WeightedUnionFind<A> uf(n);

    while (q--) {
        cin >> com;

        if (com == 0) {
            cin >> x >> y >> w;
            uf.unite(x, y, w);
        } else {
            cin >> x >> y;

            if (uf.same(x, y)) {
                cout << uf.diff(x, y) << '\n';
            } else {
                cout << "?\n";
            }
        }
    }

    return 0;
};

Back to top page