test/DataStructure/weighted_union_find/aoj-DSL_1_B.cpp

View this file on GitHub
Last update: 2024-10-01 20:26:27+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

Depends on

重み付きUnion Find (DataStructure/weighted_union_find.hpp)

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

#include "DataStructure/weighted_union_find.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;

    WeightedUnionFind 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.merge(x, y, z);
        }
        if (t == 1)
        {
            int x, y;
            cin >> x >> y;
            if (!wuf.same(x, y))
            {
                cout << "?" << endl;
            }
            else
            {
                cout << wuf.diff(x, y) << endl;
            }
        }
    }

    return 0;
}

#line 1 "test/DataStructure/weighted_union_find/aoj-DSL_1_B.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

#line 1 "DataStructure/weighted_union_find.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class T = long long>
struct WeightedUnionFind
{
public:
    WeightedUnionFind() : _n(0) {}
    explicit WeightedUnionFind(int n, T e = 0) : _n(n), parent_or_size(n, -1), diff_weight(n, e) {}

    int merge(int a, int b, T w)
    {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        assert(valid(a, b, w));

        int x = leader(a), y = leader(b);
        if (same(a, b))
        {
            return x;
        }

        w += weight(a), w -= weight(b);
        if (x == y)
        {
            return x;
        }
        if (-parent_or_size[x] < -parent_or_size[y])
        {
            swap(x, y), w *= -1;
        }
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        diff_weight[y] = w;
        return x;
    }

    bool same(int a, int b)
    {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    bool valid(int a, int b, T w)
    {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return !same(a, b) || diff(a, b) == w;
    }

    int leader(int a)
    {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0)
        {
            return a;
        }
        int r = leader(parent_or_size[a]);
        diff_weight[a] += diff_weight[parent_or_size[a]];
        return parent_or_size[a] = r;
    }

    int size(int a)
    {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    T weight(int a)
    {
        assert(0 <= a && a < _n);
        leader(a);
        return diff_weight[a];
    }

    T diff(int a, int b)
    {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        assert(same(a, b));
        return weight(b) - weight(a);
    }

    vector<vector<int>> groups()
    {
        vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++)
        {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        vector<vector<int>> result(_n);
        for (int i = 0; i < _n; i++)
        {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++)
        {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            remove_if(result.begin(), result.end(),
                      [&](const vector<int> &v)
                      { return v.empty(); }),
            result.end());
        return result;
    }

private:
    int _n;
    vector<int> parent_or_size;
    vector<T> diff_weight;
};
#line 5 "test/DataStructure/weighted_union_find/aoj-DSL_1_B.cpp"

using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;

    WeightedUnionFind 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.merge(x, y, z);
        }
        if (t == 1)
        {
            int x, y;
            cin >> x >> y;
            if (!wuf.same(x, y))
            {
                cout << "?" << endl;
            }
            else
            {
                cout << wuf.diff(x, y) << endl;
            }
        }
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	3 MB
g++	01_small_00.in	AC	4 ms	3 MB
g++	02_corner_00.in	AC	4 ms	3 MB
g++	03_general_00.in	AC	4 ms	3 MB
g++	04_rand_00.in	AC	5 ms	3 MB
g++	04_rand_01.in	AC	4 ms	3 MB
g++	04_rand_02.in	AC	4 ms	3 MB
g++	04_rand_03.in	AC	4 ms	3 MB
g++	04_rand_04.in	AC	5 ms	3 MB
g++	04_rand_05.in	AC	5 ms	3 MB
g++	04_rand_06.in	AC	5 ms	3 MB
g++	04_rand_07.in	AC	5 ms	3 MB
g++	05_large_00.in	AC	67 ms	4 MB
g++	05_large_01.in	AC	49 ms	4 MB
g++	06_maximum_00.in	AC	123 ms	4 MB
g++	06_maximum_02.in	AC	133 ms	4 MB
g++	07_dense_00.in	AC	18 ms	3 MB
g++	07_dense_01.in	AC	31 ms	4 MB
g++	07_dense_02.in	AC	72 ms	4 MB
g++	07_dense_03.in	AC	114 ms	4 MB
g++	08_shell_00.in	AC	260 ms	4 MB
g++	09_extreme_line_00.in	AC	193 ms	4 MB
g++	09_extreme_same_00.in	AC	230 ms	4 MB
g++	09_extreme_same_01.in	AC	226 ms	4 MB