cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AOJ/3022.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/3022"

#include "../../Src/Graph/Components/BlockCutTree.hpp"
using namespace zawa;

#include <iostream>
#include <numeric>
#include <vector>
#include <unordered_set>

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N, M;
    std::cin >> N >> M;
    std::vector<int> W(N);
    for (auto& w : W) std::cin >> w;
    std::vector<std::vector<int>> g(N);
    for (int i = 0 ; i < M ; i++) {
        int u, v;
        std::cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    BlockCutTree bct{g};
    const long long sum = std::accumulate(W.begin(), W.end(), 0LL);
    std::vector<long long> ans(N);
    for (int i = 0 ; i < N ; i++) if (!bct.isCut(i)) 
        ans[i] = sum - W[i];
    std::vector<bool> vis(bct.size());
    auto rec = [&](auto rec, int v, int p) -> std::pair<std::unordered_set<int>, long long> {
        vis[v] = true;
        long long s = 0LL;
        std::unordered_set<int> set;
        const int pos = bct.type(v) == decltype(bct)::Type::CUT ? bct.cut(v) : -1;
        for (int x : bct[v]) if (x != p) {
            auto [st, k] = rec(rec, x, v);
            if (pos != -1) ans[pos] = std::max(ans[pos], k - (st.contains(pos) ? W[pos] : 0));
            if (set.size() < st.size()) {
                std::swap(set, st);
                std::swap(s, k);
            }
            for (int ch : st) if (!set.contains(ch)) {
                s += W[ch];
                set.insert(ch);
            }
        }
        for (int cur : bct.vertices(v)) {
            if (!set.contains(cur)) {
                set.insert(cur);
                s += W[cur];
            }
        }
        if (pos != -1) ans[pos] = std::max(ans[pos], sum - s);
        return {set, s};
    };
    for (int i = 0 ; i < std::ssize(bct) ; i++) if (!vis[i]) rec(rec, i, -1);
    for (long long i : ans) std::cout << i << '\n';
}
#line 1 "Test/AOJ/3022.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/3022"

#line 2 "Src/Graph/Components/BlockCutTree.hpp"

#include <cassert>
#include <concepts>
#include <vector>
#include <optional>

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 9 "Src/Graph/Components/BlockCutTree.hpp"

namespace zawa {

template <std::integral T>
class BlockCutTree {
public:

    BlockCutTree() = default;

    explicit BlockCutTree(const std::vector<std::vector<T>>& g) : inv_(g.size()) {
        const usize n = g.size();
        std::vector<usize> low(n), ord(n), vs;
        usize time = 1;
        const T INVALID = static_cast<T>(-1);
        auto dfs = [&](auto dfs, T v, T p) -> void {
            low[v] = ord[v] = time++;
            if (g[v].empty()) {
                blocks_.push_back({T{v}});
                return;
            }
            usize deg = 0;
            bool cut = false;
            for (T x : g[v]) {
                if (ord[x]) {
                    low[v] = std::min(low[v], ord[x]);
                }
                else {
                    deg++;
                    dfs(dfs, x, v);
                    low[v] = std::min(low[v], low[x]);
                    if (low[x] >= ord[v]) {
                        std::vector<T> cur{v};
                        cut |= p != INVALID;
                        while (vs.size() and ord[vs.back()] >= ord[x]) {
                            cur.push_back(vs.back());
                            vs.pop_back();
                        }
                        blocks_.push_back(std::move(cur));
                    }
                }
            }
            cut |= p == INVALID and deg >= 2;
            if (cut) cuts_.push_back(v);
            vs.push_back(v);
        };
        for (T i = 0 ; i < static_cast<T>(n) ; i++) if (!ord[i]) 
            dfs(dfs, i, INVALID);
        const usize m = blocks_.size(), k = cuts_.size();
        for (usize i = 0 ; i < k ; i++) inv_[cuts_[i]] = m + i;
        g_.resize(m + k);
        for (usize i = 0 ; i < m ; i++) {
            for (T v : blocks_[i]) if (inv_[v] >= m) {
                g_[i].push_back(inv_[v]);
                g_[inv_[v]].push_back(i);
            }
        }
    }

    inline usize size() const noexcept {
        return g_.size();
    }

    const std::vector<T>& operator[](usize i) const {
        assert(i < size());
        return g_[i];
    }

    enum class Type {
        BLOCK,
        CUT
    };

    Type type(usize i) const {
        assert(i < size());
        return i < blocks_.size() ? Type::BLOCK : Type::CUT;
    }

    const std::vector<std::vector<T>>& blocks() const {
        return blocks_;
    }

    const std::vector<T>& block(usize i) const {
        assert(i < size() and type(i) == Type::BLOCK);
        return blocks_[i];
    }

    const std::vector<T>& cuts() const {
        return cuts_;
    }

    const T cut(usize i) const {
        assert(i < size() and type(i) == Type::CUT);
        return cuts_[i - blocks_.size()];
    }

    std::vector<T> vertices(usize i) const {
        assert(i < size());
        return i < blocks_.size() ? 
            blocks_[i] : std::vector<T>{cuts_[i - blocks_.size()]};
    }

    bool isCut(T v) const {
        assert(v < static_cast<T>(inv_.size()));
        return inv_[v] >= blocks_.size();
    }

    std::optional<usize> cutId(usize i) const {
        assert(i < size());
        return isCut(i) ? std::optional<usize>{inv_[i]} : std::nullopt;
    }

private:

    std::vector<std::vector<T>> blocks_;

    std::vector<T> cuts_;

    std::vector<std::vector<T>> g_;

    std::vector<usize> inv_;
};

} // namespace zawa
#line 4 "Test/AOJ/3022.test.cpp"
using namespace zawa;

#include <iostream>
#include <numeric>
#line 9 "Test/AOJ/3022.test.cpp"
#include <unordered_set>

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N, M;
    std::cin >> N >> M;
    std::vector<int> W(N);
    for (auto& w : W) std::cin >> w;
    std::vector<std::vector<int>> g(N);
    for (int i = 0 ; i < M ; i++) {
        int u, v;
        std::cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    BlockCutTree bct{g};
    const long long sum = std::accumulate(W.begin(), W.end(), 0LL);
    std::vector<long long> ans(N);
    for (int i = 0 ; i < N ; i++) if (!bct.isCut(i)) 
        ans[i] = sum - W[i];
    std::vector<bool> vis(bct.size());
    auto rec = [&](auto rec, int v, int p) -> std::pair<std::unordered_set<int>, long long> {
        vis[v] = true;
        long long s = 0LL;
        std::unordered_set<int> set;
        const int pos = bct.type(v) == decltype(bct)::Type::CUT ? bct.cut(v) : -1;
        for (int x : bct[v]) if (x != p) {
            auto [st, k] = rec(rec, x, v);
            if (pos != -1) ans[pos] = std::max(ans[pos], k - (st.contains(pos) ? W[pos] : 0));
            if (set.size() < st.size()) {
                std::swap(set, st);
                std::swap(s, k);
            }
            for (int ch : st) if (!set.contains(ch)) {
                s += W[ch];
                set.insert(ch);
            }
        }
        for (int cur : bct.vertices(v)) {
            if (!set.contains(cur)) {
                set.insert(cur);
                s += W[cur];
            }
        }
        if (pos != -1) ans[pos] = std::max(ans[pos], sum - s);
        return {set, s};
    };
    for (int i = 0 ; i < std::ssize(bct) ; i++) if (!vis[i]) rec(rec, i, -1);
    for (long long i : ans) std::cout << i << '\n';
}
Back to top page