Algorithms

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

View the Project on GitHub HyunjaeLee/Algorithms

:heavy_check_mark: graph/potentialized_offline_dynamic_connectivity.hpp

Depends on

Verified with

Code

#ifndef POTENTIALIZED_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#define POTENTIALIZED_OFFLINE_DYNAMIC_CONNECTIVITY_HPP

#include "data_structures/potentialized_rollback_dsu.hpp"
#include <algorithm>
#include <cassert>
#include <ranges>
#include <tuple>
#include <vector>

// A is an abelian group
template <typename A> struct PotentializedOfflineDynamicConnectivity {
    explicit PotentializedOfflineDynamicConnectivity(int n) : n_(n), timer_(0) {}
    void toggle_edge(int u, int v, A w) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        if (u > v) {
            std::swap(u, v);
            w = A::inv(w);
        }
        edges_.emplace_back(u, v, timer_, w);
    }
    int snapshot() { return timer_++; }
    void reserve(int n) { edges_.reserve(n); }
    void solve(auto f) {
        auto k = timer_;
        if (k == 0) {
            return;
        }
        auto comp = [](const auto &a, const auto &b) {
            const auto &[u1, v1, t1, w1] = a;
            const auto &[u2, v2, t2, w2] = b;
            return std::tie(u1, v1, t1) < std::tie(u2, v2, t2);
        };
        std::ranges::sort(edges_, comp);
        std::vector<std::vector<int>> segment(2 * k);
        const auto E = int(edges_.size());
        for (auto i = 0; i < E; ++i) {
            auto [u, v, l, w] = edges_[i];
            auto r = k;
            if (i + 1 < E && u == std::get<0>(edges_[i + 1]) && v == std::get<1>(edges_[i + 1])) {
                r = std::get<2>(edges_[++i]);
            }
            l += k;
            r += k;
            while (l < r) {
                if (l & 1) {
                    segment[l++].emplace_back(i);
                }
                if (r & 1) {
                    segment[--r].emplace_back(i);
                }
                l >>= 1;
                r >>= 1;
            }
        }
        PotentializedRollbackDSU<A> dsu(n_);
        auto dfs = [&](auto self, int node) -> void {
            auto count = 0;
            for (auto i : segment[node]) {
                auto &&[u, v, _, w] = edges_[i];
                count += dsu.merge(u, v, w);
            }
            if (node < k) {
                self(self, 2 * node);
                self(self, 2 * node + 1);
            } else {
                f(dsu, node - k);
            }
            dsu.rollback(count);
        };
        dfs(dfs, 1);
    }

private:
    int n_, timer_;
    std::vector<std::tuple<int, int, int, A>> edges_;
};

#endif // POTENTIALIZED_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#line 1 "graph/potentialized_offline_dynamic_connectivity.hpp"



#line 1 "data_structures/potentialized_rollback_dsu.hpp"



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

// A is an abelian group
template <typename A> struct PotentializedRollbackDSU {
    explicit PotentializedRollbackDSU(int n)
        : n_(n), valid_(true), parent_or_size_(n, -1), potential_(n, A::e()) {}
    int leader(int u) const { return parent_or_size_[u] < 0 ? u : leader(parent_or_size_[u]); }
    // returns p_u
    A potential(int u) const {
        return parent_or_size_[u] < 0 ? A::e()
                                      : A::op(potential_[u], potential(parent_or_size_[u]));
    }
    // returns p_v - p_u
    A diff(int u, int v) const {
        auto p_u = potential(u);
        auto p_v = potential(v);
        return A::op(p_v, A::inv(p_u));
    }
    // returns history accumulation count for offline dynamic connectivity
    // p_u + w = p_v
    int merge(int u, int v, A w) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        auto p_v = A::op(A::op(potential(u), w), A::inv(potential(v)));
        u = leader(u);
        v = leader(v);
        if (u == v) {
            history_.emplace_back(-1, 0, valid_);
            if (!(p_v == A::e())) {
                valid_ = false;
            }
            return 1;
        }
        // insert tree v into tree u
        if (-parent_or_size_[u] < -parent_or_size_[v]) {
            std::swap(u, v);
            p_v = A::inv(p_v);
        }
        history_.emplace_back(v, parent_or_size_[v], valid_);
        parent_or_size_[u] += parent_or_size_[v];
        parent_or_size_[v] = u;
        potential_[v] = p_v;
        return 1;
    }
    bool same(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        return leader(u) == leader(v);
    }
    int size(int u) const {
        assert(0 <= u && u < n_);
        return -parent_or_size_[leader(u)];
    }
    void rollback() {
        assert(!history_.empty());
        auto [v, size, valid] = history_.back();
        if (~v) {
            auto u = parent_or_size_[v];
            parent_or_size_[v] = size;
            parent_or_size_[u] -= size;
            potential_[v] = A::e();
        } else {
            valid_ = valid;
        }
        history_.pop_back();
    }
    void rollback(int count) {
        for (auto i = 0; i < count; ++i) {
            rollback();
        }
    }
    bool is_valid() const { return valid_; }

private:
    int n_;
    bool valid_;
    std::vector<int> parent_or_size_;
    std::vector<A> potential_;
    std::vector<std::tuple<int, int, bool>> history_;
};


#line 7 "graph/potentialized_offline_dynamic_connectivity.hpp"
#include <ranges>
#line 10 "graph/potentialized_offline_dynamic_connectivity.hpp"

// A is an abelian group
template <typename A> struct PotentializedOfflineDynamicConnectivity {
    explicit PotentializedOfflineDynamicConnectivity(int n) : n_(n), timer_(0) {}
    void toggle_edge(int u, int v, A w) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        if (u > v) {
            std::swap(u, v);
            w = A::inv(w);
        }
        edges_.emplace_back(u, v, timer_, w);
    }
    int snapshot() { return timer_++; }
    void reserve(int n) { edges_.reserve(n); }
    void solve(auto f) {
        auto k = timer_;
        if (k == 0) {
            return;
        }
        auto comp = [](const auto &a, const auto &b) {
            const auto &[u1, v1, t1, w1] = a;
            const auto &[u2, v2, t2, w2] = b;
            return std::tie(u1, v1, t1) < std::tie(u2, v2, t2);
        };
        std::ranges::sort(edges_, comp);
        std::vector<std::vector<int>> segment(2 * k);
        const auto E = int(edges_.size());
        for (auto i = 0; i < E; ++i) {
            auto [u, v, l, w] = edges_[i];
            auto r = k;
            if (i + 1 < E && u == std::get<0>(edges_[i + 1]) && v == std::get<1>(edges_[i + 1])) {
                r = std::get<2>(edges_[++i]);
            }
            l += k;
            r += k;
            while (l < r) {
                if (l & 1) {
                    segment[l++].emplace_back(i);
                }
                if (r & 1) {
                    segment[--r].emplace_back(i);
                }
                l >>= 1;
                r >>= 1;
            }
        }
        PotentializedRollbackDSU<A> dsu(n_);
        auto dfs = [&](auto self, int node) -> void {
            auto count = 0;
            for (auto i : segment[node]) {
                auto &&[u, v, _, w] = edges_[i];
                count += dsu.merge(u, v, w);
            }
            if (node < k) {
                self(self, 2 * node);
                self(self, 2 * node + 1);
            } else {
                f(dsu, node - k);
            }
            dsu.rollback(count);
        };
        dfs(dfs, 1);
    }

private:
    int n_, timer_;
    std::vector<std::tuple<int, int, int, A>> edges_;
};
Back to top page