verify/ds/dsu/rollback_potentialized_dsu.test.cpp

View this file on GitHub
Last update: 2026-08-12 17:21:09+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

Depends on

Code

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

#include "../../../ds/dsu/rollback_potentialized_dsu.hpp"

#include <array>
#include <cassert>
#include <iostream>
#include <random>
#include <tuple>
#include <vector>

#include "../../../monoid/add.hpp"

namespace {

using Add = m1une::monoid::Add<long long>;
using Dsu = m1une::ds::RollbackPotentializedDsu<Add>;

struct PermutationGroup {
    using value_type = std::array<int, 3>;

    static value_type id() { return {0, 1, 2}; }

    static value_type op(const value_type& first, const value_type& second) {
        value_type result;
        for (int index = 0; index < 3; ++index) {
            result[index] = second[first[index]];
        }
        return result;
    }

    static value_type inv(const value_type& value) {
        value_type result;
        for (int index = 0; index < 3; ++index) result[value[index]] = index;
        return result;
    }
};

void noncommutative_test() {
    using Permutation = PermutationGroup::value_type;
    m1une::ds::RollbackPotentializedDsu<PermutationGroup> dsu(4);
    Permutation rotate = {1, 2, 0};
    Permutation swap_last = {0, 2, 1};
    assert(dsu.merge(0, 1, rotate));
    int state = dsu.snapshot();
    assert(dsu.merge(1, 2, swap_last));
    Permutation composed = PermutationGroup::op(rotate, swap_last);
    assert(dsu.diff(0, 2) == composed);
    assert(!dsu.merge(0, 2, PermutationGroup::op(swap_last, rotate)));
    dsu.rollback(state);
    assert(!dsu.same(0, 2));
}

void randomized_test() {
    constexpr int size = 18;
    Dsu dsu(size);
    std::vector<std::vector<long long>> graph(size, std::vector<long long>(size));
    std::vector<std::vector<bool>> edge(size, std::vector<bool>(size));
    std::vector<std::tuple<int, int, long long>> history;
    std::mt19937 random(0);

    auto rebuild = [&] {
        graph.assign(size, std::vector<long long>(size));
        edge.assign(size, std::vector<bool>(size));
        for (const auto& [first, second, difference] : history) {
            edge[first][second] = edge[second][first] = true;
            graph[first][second] = difference;
            graph[second][first] = -difference;
        }
    };

    auto naive_potential = [&](int start) {
        std::vector<bool> seen(size);
        std::vector<long long> potential(size);
        std::vector<int> stack = {start};
        seen[start] = true;
        while (!stack.empty()) {
            int vertex = stack.back();
            stack.pop_back();
            for (int next = 0; next < size; ++next) {
                if (!edge[vertex][next] || seen[next]) continue;
                seen[next] = true;
                potential[next] = potential[vertex] + graph[vertex][next];
                stack.push_back(next);
            }
        }
        return std::pair(std::move(seen), std::move(potential));
    };

    auto validate = [&] {
        for (int first = 0; first < size; ++first) {
            auto [seen, potential] = naive_potential(first);
            for (int second = 0; second < size; ++second) {
                assert(dsu.same(first, second) == seen[second]);
                if (seen[second]) {
                    assert(dsu.diff(first, second) == potential[second]);
                }
            }
        }
    };

    for (int round = 0; round < 120; ++round) {
        int state = dsu.snapshot();
        std::size_t history_size = history.size();
        int update_count = 1 + int(random() % 8);
        for (int step = 0; step < update_count; ++step) {
            int first = int(random() % size);
            int second = int(random() % size);
            auto [seen, potential] = naive_potential(first);
            long long difference = seen[second]
                ? potential[second]
                : static_cast<long long>(int(random() % 41) - 20);
            bool consistent = dsu.merge(first, second, difference);
            assert(consistent);
            if (!seen[second]) history.emplace_back(first, second, difference);
            rebuild();
            validate();
        }

        dsu.rollback(state);
        history.resize(history_size);
        rebuild();
        validate();
    }
}

}  // namespace

int main() {
    noncommutative_test();
    randomized_test();

    int vertex_count, query_count;
    std::cin >> vertex_count >> query_count;
    Dsu dsu(vertex_count);
    for (int query = 0; query < query_count; ++query) {
        int type, first, second;
        std::cin >> type >> first >> second;
        if (type == 0) {
            long long difference;
            std::cin >> difference;
            dsu.merge(first, second, difference);
        } else if (dsu.same(first, second)) {
            std::cout << dsu.diff(first, second) << '\n';
        } else {
            std::cout << "?\n";
        }
    }
}

#line 1 "verify/ds/dsu/rollback_potentialized_dsu.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B"

#line 1 "ds/dsu/rollback_potentialized_dsu.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <utility>
#include <vector>

#line 1 "monoid/concept.hpp"



#line 5 "monoid/concept.hpp"

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 12 "ds/dsu/rollback_potentialized_dsu.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsGroup Group>
    requires std::equality_comparable<typename Group::value_type>
struct RollbackPotentializedDsu {
    using T = typename Group::value_type;

   private:
    struct HistoryEntry {
        int first;
        int first_value;
        int second;
        int second_value;
        T second_diff;

        HistoryEntry(int first_index, int first_parent, int second_index,
                     int second_parent, T diff)
            : first(first_index),
              first_value(first_parent),
              second(second_index),
              second_value(second_parent),
              second_diff(std::move(diff)) {}
    };

    int _n;
    int _component_count;
    std::vector<int> _parent_or_size;
    std::vector<T> _diff_to_parent;
    std::vector<HistoryEntry> _history;
    std::vector<std::size_t> _checkpoints;

    static int check_size(int n) {
        assert(0 <= n);
        return n;
    }

    std::pair<int, T> leader_and_potential(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        T result = Group::id();
        while (_parent_or_size[vertex] >= 0) {
            result = Group::op(_diff_to_parent[vertex], result);
            vertex = _parent_or_size[vertex];
        }
        return {vertex, std::move(result)};
    }

   public:
    RollbackPotentializedDsu() : RollbackPotentializedDsu(0) {}

    explicit RollbackPotentializedDsu(int n)
        : _n(check_size(n)),
          _component_count(_n),
          _parent_or_size(_n, -1),
          _diff_to_parent(_n, Group::id()) {}

    int size() const { return _n; }
    bool empty() const { return _n == 0; }
    int component_count() const { return _component_count; }
    int snapshot_count() const { return int(_checkpoints.size()); }

    void reserve_snapshots(int count) {
        assert(0 <= count);
        _checkpoints.reserve(count);
    }

    int leader(int vertex) const {
        return leader_and_potential(vertex).first;
    }

    bool same(int first, int second) const {
        return leader(first) == leader(second);
    }

    int group_size(int vertex) const {
        return -_parent_or_size[leader(vertex)];
    }

    int size(int vertex) const { return group_size(vertex); }

    T potential(int vertex) const {
        return leader_and_potential(vertex).second;
    }

    T diff(int first, int second) const {
        assert(same(first, second));
        return Group::op(Group::inv(potential(first)), potential(second));
    }

    int parent_or_size(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        return _parent_or_size[vertex];
    }

    bool merge(int first, int second, const T& difference) {
        auto [first_root, first_potential] = leader_and_potential(first);
        auto [second_root, second_potential] = leader_and_potential(second);
        if (first_root == second_root) {
            return Group::op(Group::inv(first_potential), second_potential) == difference;
        }

        T second_from_first = Group::op(
            Group::op(first_potential, difference),
            Group::inv(second_potential)
        );
        if (-_parent_or_size[first_root] < -_parent_or_size[second_root]) {
            std::swap(first_root, second_root);
            second_from_first = Group::inv(second_from_first);
        }

        if (!_checkpoints.empty()) {
            _history.emplace_back(
                first_root, _parent_or_size[first_root], second_root,
                _parent_or_size[second_root], _diff_to_parent[second_root]
            );
        }
        _parent_or_size[first_root] += _parent_or_size[second_root];
        _parent_or_size[second_root] = first_root;
        _diff_to_parent[second_root] = std::move(second_from_first);
        --_component_count;
        return true;
    }

   private:
    void restore_one() {
        HistoryEntry entry = std::move(_history.back());
        _history.pop_back();
        _parent_or_size[entry.first] = entry.first_value;
        _parent_or_size[entry.second] = entry.second_value;
        _diff_to_parent[entry.second] = std::move(entry.second_diff);
        ++_component_count;
    }

   public:
    int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }

    void rollback(int state) {
        assert(1 <= state && state <= snapshot_count());
        while (_history.size() > _checkpoints[state - 1]) restore_one();
        _checkpoints.resize(state);
    }

    void clear_history() { _history.clear(); _checkpoints.clear(); }

    std::vector<std::vector<int>> groups() const {
        std::vector<int> leaders(_n);
        std::vector<int> sizes(_n);
        for (int vertex = 0; vertex < _n; ++vertex) {
            leaders[vertex] = leader(vertex);
            ++sizes[leaders[vertex]];
        }
        std::vector<std::vector<int>> result(_n);
        for (int vertex = 0; vertex < _n; ++vertex) {
            result[vertex].reserve(sizes[vertex]);
        }
        for (int vertex = 0; vertex < _n; ++vertex) {
            result[leaders[vertex]].push_back(vertex);
        }
        result.erase(
            std::remove_if(
                result.begin(), result.end(),
                [](const std::vector<int>& group) { return group.empty(); }
            ),
            result.end()
        );
        return result;
    }
};

}  // namespace ds
}  // namespace m1une


#line 4 "verify/ds/dsu/rollback_potentialized_dsu.test.cpp"

#include <array>
#line 7 "verify/ds/dsu/rollback_potentialized_dsu.test.cpp"
#include <iostream>
#include <random>
#include <tuple>
#line 11 "verify/ds/dsu/rollback_potentialized_dsu.test.cpp"

#line 1 "monoid/add.hpp"



namespace m1une {
namespace monoid {

// Monoid for addition (Range Sum).
template <typename T>
struct Add {
    using value_type = T;
    static constexpr bool commutative = true;

    // Returns the identity element for addition, which is 0.
    static constexpr T id() {
        return T(0);
    }

    // Returns the sum of a and b.
    static constexpr T op(const T& a, const T& b) {
        return a + b;
    }

    static constexpr T inv(const T& x) {
        return -x;
    }
};

}  // namespace monoid
}  // namespace m1une


#line 13 "verify/ds/dsu/rollback_potentialized_dsu.test.cpp"

namespace {

using Add = m1une::monoid::Add<long long>;
using Dsu = m1une::ds::RollbackPotentializedDsu<Add>;

struct PermutationGroup {
    using value_type = std::array<int, 3>;

    static value_type id() { return {0, 1, 2}; }

    static value_type op(const value_type& first, const value_type& second) {
        value_type result;
        for (int index = 0; index < 3; ++index) {
            result[index] = second[first[index]];
        }
        return result;
    }

    static value_type inv(const value_type& value) {
        value_type result;
        for (int index = 0; index < 3; ++index) result[value[index]] = index;
        return result;
    }
};

void noncommutative_test() {
    using Permutation = PermutationGroup::value_type;
    m1une::ds::RollbackPotentializedDsu<PermutationGroup> dsu(4);
    Permutation rotate = {1, 2, 0};
    Permutation swap_last = {0, 2, 1};
    assert(dsu.merge(0, 1, rotate));
    int state = dsu.snapshot();
    assert(dsu.merge(1, 2, swap_last));
    Permutation composed = PermutationGroup::op(rotate, swap_last);
    assert(dsu.diff(0, 2) == composed);
    assert(!dsu.merge(0, 2, PermutationGroup::op(swap_last, rotate)));
    dsu.rollback(state);
    assert(!dsu.same(0, 2));
}

void randomized_test() {
    constexpr int size = 18;
    Dsu dsu(size);
    std::vector<std::vector<long long>> graph(size, std::vector<long long>(size));
    std::vector<std::vector<bool>> edge(size, std::vector<bool>(size));
    std::vector<std::tuple<int, int, long long>> history;
    std::mt19937 random(0);

    auto rebuild = [&] {
        graph.assign(size, std::vector<long long>(size));
        edge.assign(size, std::vector<bool>(size));
        for (const auto& [first, second, difference] : history) {
            edge[first][second] = edge[second][first] = true;
            graph[first][second] = difference;
            graph[second][first] = -difference;
        }
    };

    auto naive_potential = [&](int start) {
        std::vector<bool> seen(size);
        std::vector<long long> potential(size);
        std::vector<int> stack = {start};
        seen[start] = true;
        while (!stack.empty()) {
            int vertex = stack.back();
            stack.pop_back();
            for (int next = 0; next < size; ++next) {
                if (!edge[vertex][next] || seen[next]) continue;
                seen[next] = true;
                potential[next] = potential[vertex] + graph[vertex][next];
                stack.push_back(next);
            }
        }
        return std::pair(std::move(seen), std::move(potential));
    };

    auto validate = [&] {
        for (int first = 0; first < size; ++first) {
            auto [seen, potential] = naive_potential(first);
            for (int second = 0; second < size; ++second) {
                assert(dsu.same(first, second) == seen[second]);
                if (seen[second]) {
                    assert(dsu.diff(first, second) == potential[second]);
                }
            }
        }
    };

    for (int round = 0; round < 120; ++round) {
        int state = dsu.snapshot();
        std::size_t history_size = history.size();
        int update_count = 1 + int(random() % 8);
        for (int step = 0; step < update_count; ++step) {
            int first = int(random() % size);
            int second = int(random() % size);
            auto [seen, potential] = naive_potential(first);
            long long difference = seen[second]
                ? potential[second]
                : static_cast<long long>(int(random() % 41) - 20);
            bool consistent = dsu.merge(first, second, difference);
            assert(consistent);
            if (!seen[second]) history.emplace_back(first, second, difference);
            rebuild();
            validate();
        }

        dsu.rollback(state);
        history.resize(history_size);
        rebuild();
        validate();
    }
}

}  // namespace

int main() {
    noncommutative_test();
    randomized_test();

    int vertex_count, query_count;
    std::cin >> vertex_count >> query_count;
    Dsu dsu(vertex_count);
    for (int query = 0; query < query_count; ++query) {
        int type, first, second;
        std::cin >> type >> first >> second;
        if (type == 0) {
            long long difference;
            std::cin >> difference;
            dsu.merge(first, second, difference);
        } else if (dsu.same(first, second)) {
            std::cout << dsu.diff(first, second) << '\n';
        } else {
            std::cout << "?\n";
        }
    }
}

m1une's library

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

verify/ds/dsu/rollback_potentialized_dsu.test.cpp

Depends on

Code