#596715 (C++17) No.1326 ふたりのDominator

提出ソース
結果

問題	No.1326 ふたりのDominator
ユーザー	Pachicobue
提出日時	2020-12-23 01:28:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	169 ms / 2,000 ms
コード長	15,039 bytes
コンパイル時間	3,228 ms
コンパイル使用メモリ	238,628 KB
実行使用メモリ	44,396 KB
最終ジャッジ日時	2024-09-23 03:00:25
合計ジャッジ時間	6,074 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	4 ms 6,940 KB
testcase_09	AC	3 ms 6,940 KB
testcase_10	AC	3 ms 6,944 KB
testcase_11	AC	4 ms 6,940 KB
testcase_12	AC	168 ms 29,468 KB
testcase_13	AC	169 ms 28,900 KB
testcase_14	AC	159 ms 29,952 KB
testcase_15	AC	152 ms 29,020 KB
testcase_16	AC	141 ms 28,400 KB
testcase_17	AC	108 ms 21,796 KB
testcase_18	AC	84 ms 16,756 KB
testcase_19	AC	73 ms 19,852 KB
testcase_20	AC	130 ms 41,540 KB
testcase_21	AC	134 ms 41,680 KB
testcase_22	AC	155 ms 44,396 KB
testcase_23	AC	100 ms 21,700 KB
testcase_24	AC	165 ms 28,928 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using ld = long double;
template<typename T> using max_heap = std::priority_queue<T>;
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; }
constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; }
constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); }
constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; }
constexpr ull ceil2(const ull v) { return 1ULL << clog(v); }
constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; }
constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; }
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }
template<typename T> constexpr T inf_v = std::numeric_limits<T>::max() / 4;
template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};
template<typename T> constexpr T TEN(const int n) { return n == 0 ? T{1} : TEN<T>(n - 1) * T{10}; }
template<typename F> struct fix : F
{
    fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T, int n, int i = 0>
auto nd_array(int const (&szs)[n], const T x = T{})
{
    if constexpr (i == n) {
        return x;
    } else {
        return std::vector(szs[i], nd_array<T, n, i + 1>(szs, x));
    }
}
class printer
{
public:
    printer(std::ostream& os_ = std::cout) : m_os{os_} { m_os << std::fixed << std::setprecision(15); }
    template<typename... Args> int ln(const Args&... args) { return dump(args...), m_os << '\n', 0; }
    template<typename... Args> int el(const Args&... args) { return dump(args...), m_os << std::endl, 0; }
private:
    template<typename T> void dump(const T& v) { m_os << v; }
    template<typename T> void dump(const std::vector<T>& vs)
    {
        for (int i = 0; i < (int)vs.size(); i++) { m_os << (i ? " " : ""), dump(vs[i]); }
    }
    template<typename T> void dump(const std::vector<std::vector<T>>& vss)
    {
        for (int i = 0; i < (int)vss.size(); i++) { m_os << (0 <= i or i + 1 < (int)vss.size() ? "\n" : ""), dump(vss[i]); }
    }
    template<typename T, typename... Args> int dump(const T& v, const Args&... args) { return dump(v), m_os << ' ', dump(args...), 0; }
    std::ostream& m_os;
};
printer out;
class range
{
private:
    struct itr
    {
        itr(const int start = 0, const int step = 1) : m_cnt{start}, m_step{step} {}
        bool operator!=(const itr& it) const { return m_cnt != it.m_cnt; }
        int& operator*() { return m_cnt; }
        itr& operator++() { return m_cnt += m_step, *this; }
        int m_cnt, m_step;
    };
    int m_start, m_end, m_step;
public:
    range(const int start, const int end, const int step = 1) : m_start{start}, m_end{end}, m_step{step}
    {
        assert(m_step != 0);
        if (m_step > 0) { m_end = m_start + std::max(m_step - 1, m_end - m_start + m_step - 1) / m_step * m_step; }
        if (m_step < 0) { m_end = m_start - std::max(-m_step - 1, m_start - m_end - m_step - 1) / (-m_step) * (-m_step); }
    }
    itr begin() const { return itr{m_start, m_step}; }
    itr end() const { return itr{m_end, m_step}; }
};
range rep(const int end, const int step = 1) { return range(0, end, step); }
range per(const int rend, const int step = -1) { return range(rend - 1, -1, step); }
class scanner
{
public:
    scanner(std::istream& is_ = std::cin) : m_is{is_} { m_is.tie(nullptr), std::ios::sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return m_is >> v, v;
    }
    template<typename T> T val(const T offset) { return val<T>() - offset; }
    template<typename T> std::vector<T> vec(const int n)
    {
        return make_v<T>(n, [this]() { return val<T>(); });
    }
    template<typename T> std::vector<T> vec(const int n, const T offset)
    {
        return make_v<T>(n, [this, offset]() { return val<T>(offset); });
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1)
    {
        return make_v<std::vector<T>>(n0, [this, n1]() { return vec<T>(n1); });
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset)
    {
        return make_v<std::vector<T>>(n0, [this, n1, offset]() { return vec<T>(n1, offset); });
    }
    template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }
    template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }
private:
    template<typename T, typename F>
    std::vector<T> make_v(const int n, F f)
    {
        std::vector<T> ans;
        for (int i = 0; i < n; i++) { ans.push_back(f()); }
        return ans;
    }
    std::istream& m_is;
};
scanner in;
template<typename T = int>
class graph
{
public:
    graph(const int sz) : m_size{sz}, m_eis(sz) {}
    void add_edge(const int u, const int v, const T c, const bool bi = false)
    {
        const int ei = (int)m_us.size();
        m_us.push_back(u), m_vs.push_back(v), m_cs.push_back(c);
        m_eis[u].push_back(ei);
        if (bi) { m_eis[v].push_back(ei); }
    }
    void add_edge(const int u, const int v, const bool bi = false) { add_edge(u, v, T{1}, bi); }
    std::tuple<int, int, T> edge(const int u, const int i) const { return std::make_tuple(u, m_us[i] ^ m_vs[i] ^ u, m_cs[i]); }
    const std::vector<int>& operator[](const int u) const { return m_eis[u]; }
    std::vector<int>& operator[](const int u) { return m_eis[u]; }
    int size() const { return m_size; }
    friend std::ostream& operator<<(std::ostream& os, const graph& g)
    {
        for (int u = 0; u < g.size(); u++) {
            for (const int ei : g[u]) {
                const auto [from, to, cost] = g.edge(u, ei);
                os << "[" << ei << "]: " << from << "->" << to << "(" << cost << ")\n";
            }
        }
        return os;
    }
private:
    int m_size;
    std::vector<int> m_us, m_vs;
    std::vector<T> m_cs;
    std::vector<std::vector<int>> m_eis;
};
template<typename T>
class hl_decomp
{
public:
    hl_decomp(graph<T>& g, const int r = 0) : m_pars(g.size(), -1), m_tops{m_pars}, m_ins{m_pars}, m_ords{m_pars}, m_outs{m_pars}
    {
        const int N = g.size();
        std::vector<int> szs(N, 1);
        auto dfs1 = [&](auto self, const int u, const int p) -> int {
            m_pars[u] = p;
            for (int& ei : g[u]) {
                [[maybe_unused]] const auto& [from, to, cost] = g.edge(u, ei);
                if (p == to) { continue; }
                szs[u] += self(self, to, u);
                if (szs[std::get<1>(g.edge(u, g[u][0]))] < szs[to]) { std::swap(g[u][0], ei); }
            }
            return szs[u];
        };
        dfs1(dfs1, r, -1);
        m_tops[r] = r;
        auto dfs2 = [&](auto&& self, const int u, const int p, int& ind) -> void {
            m_ins[u] = ind++, m_ords[m_ins[u]] = u;
            for (const int ei : g[u]) {
                [[maybe_unused]] const auto& [from, to, cost] = g.edge(u, ei);
                if (to == p) { continue; }
                m_tops[to] = (ei == g[u][0] ? m_tops[u] : to);
                self(self, to, u, ind);
            }
            m_outs[u] = ind;
        };
        int ind = 0;
        dfs2(dfs2, r, -1, ind);
    }
    int pos(const int v) const { return m_ins[v]; }
    int at(const int n) const { return m_ords[n]; }
    std::pair<int, int> sub(const int v) const { return {m_ins[v], m_outs[v]}; }
    std::vector<std::pair<int, int>> path(int u, int v) const
    {
        using P = std::pair<int, int>;
        std::vector<P> head, tail;
        for (int pu = m_tops[u], pv = m_tops[v]; pu != pv;) {
            if (m_ins[pu] < m_ins[pv]) {
                tail.push_back({m_ins[pv], m_ins[v]});
                v = m_pars[pv], pv = m_tops[v];
            } else {
                head.push_back({m_ins[u], m_ins[pu]});
                u = m_pars[pu], pu = m_tops[u];
            }
        }
        head.push_back({m_ins[u], m_ins[v]});
        std::reverse(tail.begin(), tail.end());
        for (const auto& p : tail) { head.push_back(p); }
        return head;
    }
    friend std::ostream& operator<<(std::ostream& os, const hl_decomp& hld)
    {
        os << "ord = {";
        for (const int v : hld.m_ords) { os << v << ","; }
        os << "}\ntops = {";
        for (const int v : hld.m_tops) { os << v << ","; }
        return os << "}";
    }
private:
    std::vector<int> m_pars, m_tops, m_ins, m_ords, m_outs;
};
template<typename T>
class static_rsq
{
public:
    static_rsq() = default;
    void push_back(const T& v) { m_sums.push_back(m_sums.back() + v); }
    T operator()(const int l, const int r) const { return m_sums[r] - m_sums[l]; }
private:
    std::vector<T> m_sums{T{}};
};
using namespace std;
class Articulation
{
public:
    struct bcnode;
private:
    const int V;
    vector<int> ord, low;
    bool check(const int u)
    {
        for (const int v : G[u]) {
            if (ord[v] < 0) return true;
        }
        return false;
    }
    void identify_block(const int u, const int v, bool* used, stack<pair<int, int>>& st, const vector<int>& bcnode_id)
    {
        vector<pair<int, int>> block;
        vector<int> cut_vertex;
        while (!st.empty()) {
            const pair<int, int> p = st.top();
            st.pop(), block.push_back(p);
            if (art[p.first] && !used[p.first]) {
                cut_vertex.push_back(p.first);
                used[p.first] = true;
            }
            if (art[p.second] && !used[p.second]) {
                cut_vertex.push_back(p.second);
                used[p.second] = true;
            }
            if (p == (pair<int, int>){u, v}) break;
        }
        const int block_id = (int)bctree.size();
        bctree.push_back(vector<int>());
        bcnodes.emplace_back(true, move(block));
        for (const int ver : cut_vertex) {
            bctree[block_id].push_back(bcnode_id[ver]);
            bctree[bcnode_id[ver]].push_back(block_id);
            used[ver] = false;
        }
    }
    void dfs(const int u, const int p, int& tm, bool* used, stack<pair<int, int>>& st, vector<int>& bcnode_id)
    {
        ord[u] = low[u] = tm++;
        bool multi_edge = false;
        for (const int v : G[u]) {
            if (ord[v] < 0) {
                st.push({u, v});
                dfs(v, u, tm, used, st, bcnode_id);
                low[u] = min(low[u], low[v]);
                if (ord[u] <= low[v]) {
                    if (!art[u] && (p >= 0 || check(u))) {
                        art[u] = true;
                        bcnode_id[u] = (int)bctree.size();
                        bctree.push_back(vector<int>());
                        bcnodes.emplace_back(false, vector<pair<int, int>>{{u, u}});
                    }
                    identify_block(u, v, used, st, bcnode_id);
                }
            } else if (v == p) {
                if (multi_edge) {
                    st.push({u, v});
                    low[u] = min(low[u], ord[v]);
                } else {
                    multi_edge = true;
                }
            } else if (ord[v] < ord[u]) {
                st.push({u, v});
                low[u] = min(low[u], ord[v]);
            }
        }
    }
public:
    vector<vector<int>> G;
    vector<bool> art;
    struct bcnode
    {
        bool isBlock;
        vector<pair<int, int>> component;
        friend std::ostream& operator<<(std::ostream& os, const bcnode& node)
        {
            os << (node.isBlock ? "Block" : "Cut") << ":[";
            for (const auto& [u, v] : node.component) { os << "<" << u << "," << v << ">"; }
            os << "]\n";
            return os;
        }
        bcnode(bool _isBlock, vector<pair<int, int>>&& _component)
            : isBlock(_isBlock), component(move(_component)) {}
    };
    vector<vector<int>> bctree;
    vector<bcnode> bcnodes;
    Articulation(const int node_size)
        : V(node_size), ord(V, -1), low(V), G(V), art(V, false) {}
    void add_edge(const int a, const int b)
    {
        G[a].push_back(b), G[b].push_back(a);
    }
    int solve()
    {
        int tm = 0;
        bool* used = new bool[V]();
        stack<pair<int, int>> st;
        vector<int> bcnode_id(V, -1);
        for (int i = 0; i < V; ++i) {
            if (ord[i] < 0) dfs(i, -1, tm, used, st, bcnode_id);
            if (G[i].empty()) {
                bctree.push_back(vector<int>());
                bcnodes.emplace_back(true, vector<pair<int, int>>());
            }
        }
        delete[] used;
        return (int)bctree.size();
    }
};
int main()
{
    const auto [N, M] = in.tup<int, int>();
    std::vector<int> us(M), vs(M);
    Articulation arts(N);
    for (const int i : rep(M)) {
        const auto [u, v] = in.tup<int, int>(1, 1);
        arts.add_edge(u, v);
    }
    arts.solve();
    static_cast<void>(0);
    static_cast<void>(0);
    static_cast<void>(0);
    const int v = arts.bcnodes.size();
    std::vector<int> cs(N);
    std::vector<std::vector<int>> vss(v);
    for (const int i : rep(v)) {
        if (arts.bcnodes[i].isBlock) {
            const auto es = arts.bcnodes[i].component;
            for (const auto [u, v] : es) {
                if (not arts.art[u]) { cs[u] = i; }
                if (not arts.art[v]) { cs[v] = i; }
            }
        } else {
            cs[arts.bcnodes[i].component[0].first] = i;
        }
    }
    for (const int i : rep(N)) { vss[cs[i]].push_back(i); }
    static_cast<void>(0);
    static_cast<void>(0);
    graph g(v);
    for (const int i : rep(v)) {
        for (const int j : arts.bctree[i]) { g.add_edge(i, j); }
    }
    hl_decomp hld(g);
    static_rsq<int> rsq;
    std::vector<int> is(v), ws(v);
    for (const int i : rep(v)) {
        const int c = hld.at(i);
        int sum = 0;
        for (const int v : vss[c]) { sum += arts.art[v]; }
        rsq.push_back(sum);
        is[i] = c, ws[i] = sum;
    }
    static_cast<void>(0);
    static_cast<void>(0);
    const auto Q = in.val<int>();
    for (const int q : rep(Q)) {
        const auto [x, y] = in.tup<int, int>(1, 1);
        const int cx = cs[x], cy = cs[y];
        if (cx == cy) {
            out.ln(0);
        } else {
            const auto rs = hld.path(cx, cy);
            int num = 0;
            for (auto [l, r] : rs) {
                if (l > r) { std::swap(l, r); }
                r++;
                static_cast<void>(0);
                num += rsq(l, r);
            }
            if (arts.art[x]) { num--; }
            if (arts.art[y]) { num--; }
            out.ln(num);
        }
    }
    return 0;
}
yukicoder

結果

テストケース

ソースコード
