library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/weighted_dsu.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <optional>
#include <random>
#include <vector>

#include "algebra/group_add.hpp"
#include "algebra/group_xor.hpp"
#include "datastructure/weighted_dsu.hpp"

// brute force: potentials via BFS over accepted constraints
template <class G> struct brute {
    using S = typename G::S;
    int n;
    std::vector<std::vector<std::pair<int, S>>> g;  // (to, diff(from, to))
    explicit brute(int n) : n(n), g(n) {
    }
    std::vector<std::optional<S>> potentials(int s) {
        std::vector<std::optional<S>> p(n);
        p[s] = G::e();
        std::vector<int> st = {s};
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            for (auto [u, w] : g[v]) {
                if (p[u]) continue;
                p[u] = G::op(*p[v], w);
                st.push_back(u);
            }
        }
        return p;
    }
    bool merge(int a, int b, S w) {
        auto p = potentials(a);
        if (p[b]) return *p[b] == w;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, G::inv(w));
        return true;
    }
    std::optional<S> diff(int a, int b) {
        return potentials(a)[b];
    }
};

template <class G> void run(std::mt19937& rng, auto gen) {
    for (int it = 0; it < 300; it++) {
        int n = 1 + rng() % 8;
        weighted_dsu<G> d(n);
        brute<G> b(n);
        for (int q = 0; q < 30; q++) {
            int x = rng() % n, y = rng() % n;
            if (rng() % 2) {
                auto w = gen();
                assert(d.merge(x, y, w) == b.merge(x, y, w));
            } else {
                auto r = b.diff(x, y);
                assert(d.same(x, y) == r.has_value());
                if (r) assert(d.diff(x, y) == *r);
            }
        }
        auto groups = d.groups();
        int total = 0;
        for (auto& grp : groups) {
            for (int v : grp) assert(d.leader(v) == d.leader(grp[0])), assert(d.size(v) == int(grp.size()));
            total += int(grp.size());
        }
        assert(total == n);
    }
}

// non-commutative: affine maps x -> a x + b over a prime field (a != 0)
struct group_affine {
    static constexpr long long p = 1000003;
    struct S {
        long long a, b;
        bool operator==(const S&) const = default;
    };
    static long long pw(long long a, long long n) {
        long long r = 1;
        a %= p;
        while (n) {
            if (n & 1) r = r * a % p;
            a = a * a % p;
            n >>= 1;
        }
        return r;
    }
    static S op(S f, S g) {  // f after g: f(g(x))
        return {f.a * g.a % p, (f.a * g.b + f.b) % p};
    }
    static S e() {
        return {1, 0};
    }
    static S inv(S f) {
        long long ia = pw(f.a, p - 2);
        return {ia, (p - ia * f.b % p) % p};
    }
};

int main() {
    std::mt19937 rng(2024);
    run<group_add<long long>>(rng, [&] { return (long long)(rng() % 21) - 10; });
    run<group_xor<int>>(rng, [&] { return int(rng() % 16); });
    run<group_affine>(rng, [&] { return group_affine::S{1 + (long long)(rng() % 5), (long long)(rng() % 7)}; });
    // contradiction leaves the structure unchanged
    {
        weighted_dsu<group_add<long long>> d(3);
        assert(d.merge(0, 1, 5));
        assert(d.merge(1, 2, 7));
        assert(d.diff(0, 2) == 12 && d.diff(2, 0) == -12);
        assert(!d.merge(0, 2, 13));
        assert(d.merge(0, 2, 12));
        assert(d.size(0) == 3);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/unit/weighted_dsu.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <optional>
#include <random>
#include <vector>

#line 2 "algebra/monoid_add.hpp"
template <class T>
struct monoid_add {
    using S = T;
    static S op(S a, S b) {
        return a + b;
    }
    static S e() {
        return T(0);
    }
};
#line 3 "algebra/group_add.hpp"
template <class T>
struct group_add : monoid_add<T> {
    static T inv(T a) {
        return -a;
    }
};
#line 2 "algebra/monoid_xor.hpp"
template <class T>
struct monoid_xor {
    using S = T;
    static S op(S a, S b) {
        return a ^ b;
    }
    static S e() {
        return T(0);
    }
};
#line 3 "algebra/group_xor.hpp"
template <class T>
struct group_xor : monoid_xor<T> {
    static T inv(T a) {
        return a;
    }
};
#line 2 "datastructure/weighted_dsu.hpp"
#include <algorithm>
#line 4 "datastructure/weighted_dsu.hpp"
#include <utility>
#line 6 "datastructure/weighted_dsu.hpp"

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
#line 8 "datastructure/weighted_dsu.hpp"

// potential p[v] of each vertex; diff(a, b) = op(inv(p[a]), p[b])
template <group G> struct weighted_dsu {
public:
    using S = typename G::S;
    weighted_dsu() : weighted_dsu(0) {
    }
    explicit weighted_dsu(int n) : _n(n), parent_or_size(n, -1), pot(n, G::e()) {
    }
    // make diff(a, b) == w; returns false if it contradicts the existing constraints
    bool merge(int a, int b, S w) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return diff(a, b) == w;
        // p[y] relative to x: op(inv(p[a]), op(p[y], p[b])) == w
        S py = G::op(G::op(pot[a], w), G::inv(pot[b]));
        if (-parent_or_size[x] < -parent_or_size[y]) {
            std::swap(x, y);
            py = G::inv(py);
        }
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        pot[y] = py;
        return true;
    }
    S diff(int a, int b) {
        assert(same(a, b));
        return G::op(G::inv(pot[a]), pot[b]);
    }
    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }
    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        int p = parent_or_size[a];
        int r = leader(p);
        if (p != r) pot[a] = G::op(pot[p], pot[a]);
        return parent_or_size[a] = r;
    }
    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }
    std::vector<std::vector<int>> 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<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(std::remove_if(result.begin(), result.end(),
                                    [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }

private:
    int _n;
    std::vector<int> parent_or_size;
    std::vector<S> pot;  // relative to parent
};
#line 11 "test/unit/weighted_dsu.test.cpp"

// brute force: potentials via BFS over accepted constraints
template <class G> struct brute {
    using S = typename G::S;
    int n;
    std::vector<std::vector<std::pair<int, S>>> g;  // (to, diff(from, to))
    explicit brute(int n) : n(n), g(n) {
    }
    std::vector<std::optional<S>> potentials(int s) {
        std::vector<std::optional<S>> p(n);
        p[s] = G::e();
        std::vector<int> st = {s};
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            for (auto [u, w] : g[v]) {
                if (p[u]) continue;
                p[u] = G::op(*p[v], w);
                st.push_back(u);
            }
        }
        return p;
    }
    bool merge(int a, int b, S w) {
        auto p = potentials(a);
        if (p[b]) return *p[b] == w;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, G::inv(w));
        return true;
    }
    std::optional<S> diff(int a, int b) {
        return potentials(a)[b];
    }
};

template <class G> void run(std::mt19937& rng, auto gen) {
    for (int it = 0; it < 300; it++) {
        int n = 1 + rng() % 8;
        weighted_dsu<G> d(n);
        brute<G> b(n);
        for (int q = 0; q < 30; q++) {
            int x = rng() % n, y = rng() % n;
            if (rng() % 2) {
                auto w = gen();
                assert(d.merge(x, y, w) == b.merge(x, y, w));
            } else {
                auto r = b.diff(x, y);
                assert(d.same(x, y) == r.has_value());
                if (r) assert(d.diff(x, y) == *r);
            }
        }
        auto groups = d.groups();
        int total = 0;
        for (auto& grp : groups) {
            for (int v : grp) assert(d.leader(v) == d.leader(grp[0])), assert(d.size(v) == int(grp.size()));
            total += int(grp.size());
        }
        assert(total == n);
    }
}

// non-commutative: affine maps x -> a x + b over a prime field (a != 0)
struct group_affine {
    static constexpr long long p = 1000003;
    struct S {
        long long a, b;
        bool operator==(const S&) const = default;
    };
    static long long pw(long long a, long long n) {
        long long r = 1;
        a %= p;
        while (n) {
            if (n & 1) r = r * a % p;
            a = a * a % p;
            n >>= 1;
        }
        return r;
    }
    static S op(S f, S g) {  // f after g: f(g(x))
        return {f.a * g.a % p, (f.a * g.b + f.b) % p};
    }
    static S e() {
        return {1, 0};
    }
    static S inv(S f) {
        long long ia = pw(f.a, p - 2);
        return {ia, (p - ia * f.b % p) % p};
    }
};

int main() {
    std::mt19937 rng(2024);
    run<group_add<long long>>(rng, [&] { return (long long)(rng() % 21) - 10; });
    run<group_xor<int>>(rng, [&] { return int(rng() % 16); });
    run<group_affine>(rng, [&] { return group_affine::S{1 + (long long)(rng() % 5), (long long)(rng() % 7)}; });
    // contradiction leaves the structure unchanged
    {
        weighted_dsu<group_add<long long>> d(3);
        assert(d.merge(0, 1, 5));
        assert(d.merge(1, 2, 7));
        assert(d.diff(0, 2) == 12 && d.diff(2, 0) == -12);
        assert(!d.merge(0, 2, 13));
        assert(d.merge(0, 2, 12));
        assert(d.size(0) == 3);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page