test/offline_dynamic_connectivity.test.cpp

• View this file on GitHub
• Last update: 2022-09-30 17:14:09+00:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235

Depends on

• disjoint_set/rollback_disjoint_set.hpp
• graph/offline_dynamic_connectivity.hpp

Code

#include <clocale>
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235"

#include "../disjoint_set/rollback_disjoint_set.hpp"
#include "../graph/offline_dynamic_connectivity.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, k;
    std::cin >> n >> k;
    offline_dynamic_connectivity<rollback_disjoint_set> dc(n);
    std::vector<std::pair<int, int>> q;
    dc.reserve(k);
    q.reserve(k);
    while (k--) {
        int t, u, v;
        std::cin >> t >> u >> v;
        switch (t) {
        case 1:
        case 2:
            dc.toggle_edge(u, v);
            break;
        case 3:
            q.emplace_back(u, v);
            dc.snapshot();
            break;
        }
    }
    auto result = dc.solve([&](const auto &dsu, int i) {
        auto [u, v] = q[i];
        return dsu.same(u, v);
    });
    for (auto b : result) {
        std::cout << (b ? "YES\n" : "NO\n");
    }
}

#line 1 "test/offline_dynamic_connectivity.test.cpp"
#include <clocale>
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235"

#line 1 "disjoint_set/rollback_disjoint_set.hpp"



#include <cassert>
#include <stack>
#include <utility>
#include <vector>

struct rollback_disjoint_set {
    explicit rollback_disjoint_set(int n) : n_(n), parent_or_size_(n, -1) {}
    int find(int u) const {
        return parent_or_size_[u] < 0 ? u : find(parent_or_size_[u]);
    }
    bool merge(int u, int v) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        u = find(u);
        v = find(v);
        if (u == v) {
            return false;
        }
        if (-parent_or_size_[u] < -parent_or_size_[v]) {
            std::swap(u, v);
        }
        history_.emplace(v, parent_or_size_[v]);
        parent_or_size_[u] += parent_or_size_[v];
        parent_or_size_[v] = u;
        return true;
    }
    bool same(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        return find(u) == find(v);
    }
    int size(int u) const {
        assert(0 <= u && u < n_);
        return -parent_or_size_[find(u)];
    }
    void rollback() {
        assert(!history_.empty());
        auto [v, val] = history_.top();
        auto u = parent_or_size_[v];
        parent_or_size_[v] = val;
        parent_or_size_[u] -= val;
        history_.pop();
    }
    void rollback(int count) {
        for (auto i = 0; i < count; ++i) {
            rollback();
        }
    }

private:
    int n_;
    std::vector<int> parent_or_size_;
    std::stack<std::pair<int, int>> history_;
};


#line 1 "graph/offline_dynamic_connectivity.hpp"



#include <algorithm>
#include <array>
#line 7 "graph/offline_dynamic_connectivity.hpp"
#include <type_traits>
#line 10 "graph/offline_dynamic_connectivity.hpp"

template <typename DisjointSet> struct offline_dynamic_connectivity {
    explicit offline_dynamic_connectivity(int n) : n_(n), timer_(0) {}
    void toggle_edge(int u, int v) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        if (u > v) {
            std::swap(u, v);
        }
        edges_.push_back({u, v, timer_});
    }
    int snapshot() { return timer_++; }
    void reserve(int n) { edges_.reserve(n); }
    template <typename Function>
    std::vector<std::invoke_result_t<Function, DisjointSet, int>>
    solve(Function f) {
        auto k = timer_;
        if (k == 0) {
            return {};
        }
        std::sort(edges_.begin(), edges_.end());
        std::vector<std::vector<std::pair<int, int>>> segment(2 * k);
        auto edges_size = static_cast<int>(edges_.size());
        for (auto i = 0; i < edges_size; ++i) {
            auto [u, v, l] = edges_[i];
            auto r = k;
            if (i + 1 < edges_size && u == edges_[i + 1][0] &&
                v == edges_[i + 1][1]) {
                r = edges_[++i][2];
            }
            l += k;
            r += k;
            while (l < r) {
                if (l & 1) {
                    segment[l++].push_back({u, v});
                }
                if (r & 1) {
                    segment[--r].push_back({u, v});
                }
                l >>= 1;
                r >>= 1;
            }
        }
        DisjointSet dsu(n_);
        std::vector<std::invoke_result_t<Function, DisjointSet, int>> result(k);
        auto dfs = [&](auto self, int node) -> void {
            auto count = 0;
            for (auto [u, v] : segment[node]) {
                if (dsu.merge(u, v)) {
                    ++count;
                }
            }
            if (node < k) {
                self(self, 2 * node);
                self(self, 2 * node + 1);
            } else {
                result[node - k] = f(dsu, node - k);
            }
            dsu.rollback(count);
        };
        dfs(dfs, 1);
        return result;
    }

private:
    int n_, timer_;
    std::vector<std::array<int, 3>> edges_;
};


#line 6 "test/offline_dynamic_connectivity.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, k;
    std::cin >> n >> k;
    offline_dynamic_connectivity<rollback_disjoint_set> dc(n);
    std::vector<std::pair<int, int>> q;
    dc.reserve(k);
    q.reserve(k);
    while (k--) {
        int t, u, v;
        std::cin >> t >> u >> v;
        switch (t) {
        case 1:
        case 2:
            dc.toggle_edge(u, v);
            break;
        case 3:
            q.emplace_back(u, v);
            dc.snapshot();
            break;
        }
    }
    auto result = dc.solve([&](const auto &dsu, int i) {
        auto [u, v] = q[i];
        return dsu.same(u, v);
    });
    for (auto b : result) {
        std::cout << (b ? "YES\n" : "NO\n");
    }
}

Back to top page