rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: unionfind/test/potentialized_unionfind_groups.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <iostream>

#include "../../algebra/monoid/monoid_plus.hpp"
#include "../../unionfind/potentialized_unionfind.hpp"

void test1_zero() {
    PotentializedUnionfind<MonoidPlus<int>> uf(0);
    assert(uf.groups() == (std::vector<std::vector<std::pair<int, int>>>()));
}

void test2_empty() {
    PotentializedUnionfind<MonoidPlus<int>> uf;
    assert(uf.groups() == (std::vector<std::vector<std::pair<int, int>>>()));
}

void test3_assign() {
    PotentializedUnionfind<MonoidPlus<int>> uf;
    uf = PotentializedUnionfind<MonoidPlus<int>>(10);
}

void test4_simple() {
    PotentializedUnionfind<MonoidPlus<int>> uf(2);
    assert(uf.same(0, 1) == false);
    int x = uf.merge(0, 1, 2);
    assert(uf.leader(0) == x);
    assert(uf.leader(1) == x);
    assert(uf.same(0, 1) == true);
    assert(uf.size(0) == 2);
    assert(uf.distance(0, 1) == 2);
}

void test5_line() {
    int n = 500000;
    PotentializedUnionfind<MonoidPlus<int>> uf(n);
    for (int i = 0; i < n - 1; i++) {
        uf.merge(i, i + 1, 1);
    }
    assert(uf.size(0) == n);
    assert(uf.groups().size() == 1);
    assert(uf.distance(0, n - 1) == n - 1);
}

void test6_line_reverse() {
    int n = 500000;
    PotentializedUnionfind<MonoidPlus<int>> uf(n);
    for (int i = n - 2; i >= 0; i--) {
        uf.merge(i, i + 1, 1);
    }
    assert(uf.size(0) == n);
    assert(uf.groups().size() == 1);
    assert(uf.distance(0, n - 1) == n - 1);
}

void test7_groups() {
    int n = 5;
    PotentializedUnionfind<MonoidPlus<int>> uf(n);
    uf.merge(0, 1, 1);
    uf.merge(2, 3, 2);
    uf.merge(2, 4, 6);
    auto gp = uf.groups();
    for (auto&& v : gp) {
        std::sort(v.begin(), v.end());
        int v0 = v[0].second;
        for (auto&& vi : v) {
            vi.second -= v0;
        }
    }
    std::sort(gp.begin(), gp.end());
    std::vector<std::vector<std::pair<int, int>>> gp_sorted = {
        {{0, 0}, {1, 1}}, {{2, 0}, {3, 2}, {4, 6}}};
    assert(gp == gp_sorted);
}

int main() {
    test1_zero();
    test2_empty();
    test3_assign();
    test4_simple();
    test5_line();
    test6_line_reverse();
    test7_groups();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}
#line 1 "unionfind/test/potentialized_unionfind_groups.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <iostream>

#line 2 "algebra/monoid/monoid_plus.hpp"

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};
#line 2 "unionfind/potentialized_unionfind.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

// Potentialized Unionfind
template <class G> struct PotentializedUnionfind {
    static_assert(G::commutative == true);

    using T = typename G::value_type;

    int n;
    std::vector<int> parent;
    std::vector<T> value;

    PotentializedUnionfind() = default;

    explicit PotentializedUnionfind(int n)
        : n(n), parent(n, -1), value(n, G::identity()) {}

    int leader(int x) {
        assert(0 <= x and x < n);
        if (parent[x] < 0) {
            return x;
        } else {
            int r = leader(parent[x]);
            value[x] = G::operation(value[x], value[parent[x]]);
            return parent[x] = r;
        }
    }

    T potential(int x) {
        assert(0 <= x and x < n);
        leader(x);
        return value[x];
    }

    int merge(int x, int y, T d) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        // d は y の x からのポテンシャルの差分
        // d を leader(y) の leader(x) からのポテンシャルの差分に修正
        d = G::operation(G::operation(d, potential(x)),
                         G::inverse(potential(y)));
        x = leader(x);
        y = leader(y);
        if (x == y) {
            if (d == G::identity()) {
                return x;
            } else {
                return -1;
            }
        }
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
            d = G::inverse(d);
        }
        parent[x] += parent[y];
        parent[y] = x;
        value[y] = d;
        return x;
    }

    T distance(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        assert(same(x, y));
        return G::operation(potential(y), G::inverse(potential(x)));
    }

    bool same(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        return leader(x) == leader(y);
    }

    int size(int x) {
        assert(0 <= x and x < n);
        return -parent[leader(x)];
    }

    std::vector<std::vector<std::pair<int, T>>> groups() {
        std::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]]++;
        }
        std::vector<std::vector<std::pair<int, T>>> 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]].emplace_back(i, potential(i));
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<std::pair<int, T>>& v) {
                               return v.empty();
                           }),
            result.end());
        return result;
    }
};
#line 7 "unionfind/test/potentialized_unionfind_groups.test.cpp"

void test1_zero() {
    PotentializedUnionfind<MonoidPlus<int>> uf(0);
    assert(uf.groups() == (std::vector<std::vector<std::pair<int, int>>>()));
}

void test2_empty() {
    PotentializedUnionfind<MonoidPlus<int>> uf;
    assert(uf.groups() == (std::vector<std::vector<std::pair<int, int>>>()));
}

void test3_assign() {
    PotentializedUnionfind<MonoidPlus<int>> uf;
    uf = PotentializedUnionfind<MonoidPlus<int>>(10);
}

void test4_simple() {
    PotentializedUnionfind<MonoidPlus<int>> uf(2);
    assert(uf.same(0, 1) == false);
    int x = uf.merge(0, 1, 2);
    assert(uf.leader(0) == x);
    assert(uf.leader(1) == x);
    assert(uf.same(0, 1) == true);
    assert(uf.size(0) == 2);
    assert(uf.distance(0, 1) == 2);
}

void test5_line() {
    int n = 500000;
    PotentializedUnionfind<MonoidPlus<int>> uf(n);
    for (int i = 0; i < n - 1; i++) {
        uf.merge(i, i + 1, 1);
    }
    assert(uf.size(0) == n);
    assert(uf.groups().size() == 1);
    assert(uf.distance(0, n - 1) == n - 1);
}

void test6_line_reverse() {
    int n = 500000;
    PotentializedUnionfind<MonoidPlus<int>> uf(n);
    for (int i = n - 2; i >= 0; i--) {
        uf.merge(i, i + 1, 1);
    }
    assert(uf.size(0) == n);
    assert(uf.groups().size() == 1);
    assert(uf.distance(0, n - 1) == n - 1);
}

void test7_groups() {
    int n = 5;
    PotentializedUnionfind<MonoidPlus<int>> uf(n);
    uf.merge(0, 1, 1);
    uf.merge(2, 3, 2);
    uf.merge(2, 4, 6);
    auto gp = uf.groups();
    for (auto&& v : gp) {
        std::sort(v.begin(), v.end());
        int v0 = v[0].second;
        for (auto&& vi : v) {
            vi.second -= v0;
        }
    }
    std::sort(gp.begin(), gp.end());
    std::vector<std::vector<std::pair<int, int>>> gp_sorted = {
        {{0, 0}, {1, 1}}, {{2, 0}, {3, 2}, {4, 6}}};
    assert(gp == gp_sorted);
}

int main() {
    test1_zero();
    test2_empty();
    test3_assign();
    test4_simple();
    test5_line();
    test6_line_reverse();
    test7_groups();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}
Back to top page