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

提出ソース

結果

問題	No.1326 ふたりのDominator
ユーザー	yuri3
提出日時	2023-06-27 05:29:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	126 ms / 2,000 ms
コード長	6,419 bytes
コンパイル時間	2,479 ms
コンパイル使用メモリ	225,316 KB
実行使用メモリ	42,200 KB
最終ジャッジ日時	2024-07-03 23:52:45
合計ジャッジ時間	5,097 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	AC	3 ms 6,940 KB
testcase_09	AC	3 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	3 ms 6,940 KB
testcase_12	AC	99 ms 26,592 KB
testcase_13	AC	101 ms 26,688 KB
testcase_14	AC	100 ms 26,484 KB
testcase_15	AC	100 ms 26,324 KB
testcase_16	AC	97 ms 25,420 KB
testcase_17	AC	79 ms 21,196 KB
testcase_18	AC	74 ms 17,368 KB
testcase_19	AC	61 ms 20,480 KB
testcase_20	AC	107 ms 38,408 KB
testcase_21	AC	112 ms 38,340 KB
testcase_22	AC	126 ms 42,200 KB
testcase_23	AC	75 ms 22,688 KB
testcase_24	AC	107 ms 26,460 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using i64 = std::int64_t;

template <class G>
struct BlockCutTree {
    G tree;
    std::vector<int> dfn, low;
    std::vector<int> ar;  // cut vertex 1/0
    std::vector<int> idar, idcc;

    std::vector<std::vector<int>> bcc;
    std::vector<std::vector<int>> aux;  // block cut tree
    BlockCutTree(const G& tree) : tree(tree) {
        int sz = tree.size();
        dfn.assign(sz, -1);
        low.assign(sz, -1);
        ar.assign(sz, 0);
        idar.assign(sz, -1);
        idcc.assign(sz, -1);

        build();
    }
    void build() {
        int cnt = 0;
        std::stack<int> st;
        auto dfs = [&](auto&& self, int u, int fa) -> void {
            dfn[u] = low[u] = cnt++;
            int childCnt = 0;
            st.push(u);
            for (const auto& v : tree[u]) {
                if (v == fa) continue;
                if (dfn[v] == -1) {
                    childCnt++;
                    self(self, v, u);
                    low[u] = std::min(low[u], low[v]);
                    if (low[v] >= dfn[u]) {
                        ar[u] = 1;
                        std::vector<int> curBcc;
                        while (true) {
                            int cur = st.top();
                            curBcc.push_back(cur);
                            st.pop();
                            if (cur == v) break;
                        }
                        curBcc.push_back(u);
                        bcc.push_back(curBcc);
                    }
                } else
                    low[u] = std::min(low[u], dfn[v]);
            }
            if (fa < 0 && childCnt < 2) ar[u] = 0;
        };
        for (int i = 0; i < (int)tree.size(); i++) {
            if (dfn[i] == -1) dfs(dfs, i, -1);
        }

        std::vector<int> arSet;
        for (int i = 0; i < (int)ar.size(); i++)
            if (ar[i]) arSet.push_back(i);

        for (int i = 0; i < (int)arSet.size(); i++) idar[arSet[i]] = i;

        aux.resize(arSet.size() + bcc.size());
        std::vector<int> last(tree.size(), -1);

        for (int i = 0; i < (int)bcc.size(); i++) {
            auto add = [&](int i, int j) {
                if (i == -1 or j == -1) return;
                aux[i].push_back(j);
                aux[j].push_back(i);
                return;
            };
            for (const auto& u : bcc[i]) {
                if (idar[u] == -1)
                    idcc[u] = i + (int)arSet.size();
                else if (last[u] != i) {
                    add(i + (int)arSet.size(), idar[u]);
                    last[u] = i;
                }
            }
        }
    }
    std::vector<int>& operator[](int i) { return aux[i]; }
    int size() const { return aux.size(); }
    int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; }
    bool is_arti(int i) { return idar[i] != -1; }
};

struct HLD {
    int n;
    int cnt;  // dfs order [0,n)
    std::vector<std::vector<int>> adj;
    std::vector<int> par, dfn, hson, siz, top, dep;
    HLD() = delete;
    HLD(int _n)
        : n(_n),
          cnt(0),
          adj(_n),
          par(_n),
          dfn(_n),
          hson(_n),
          siz(_n),
          top(_n),
          dep(_n){};
    HLD(std::vector<std::vector<int>> tr) {
        cnt = 0;
        n = tr.size();
        adj = tr;
        par.resize(n), dfn.resize(n), hson.resize(n), siz.resize(n),
            top.resize(n), dep.resize(n);
    }

    void addEdge(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
        return;
    }

    void build(int root = 0) {
        auto dfs1 = [&](auto&& self, int u, int fa) -> void {
            par[u] = fa, siz[u] = 1, hson[u] = -1;
            for (const auto& v : adj[u]) {
                if (v == fa) continue;
                dep[v] = dep[u] + 1;
                self(self, v, u);
                siz[u] += siz[v];
                if (hson[u] == -1)
                    hson[u] = v;
                else if (siz[hson[u]] < siz[v])
                    hson[u] = v;
            }
        };
        dfs1(dfs1, root, -1);
        auto dfs2 = [&](auto&& self, int u, int tp) -> void {
            dfn[u] = cnt++;
            top[u] = tp;
            if (hson[u] == -1) return;
            self(self, hson[u], tp);
            for (const auto& v : adj[u]) {
                if (v == par[u] || v == hson[u]) continue;
                self(self, v, v);
            }
        };
        dfs2(dfs2, root, root);
        return;
    }

    int lca(int u, int v) const {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]])
                u = par[top[u]];
            else
                v = par[top[v]];
        }
        return ((dep[u] > dep[v]) ? v : u);
    }

    std::vector<std::pair<int, int>> pathP2P(int u, int v) const {
        // op length O(logn)
        std::vector<std::pair<int, int>> op;
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
            op.emplace_back(dfn[top[u]], dfn[u]);
            u = par[top[u]];
        }
        if (dep[u] > dep[v]) std::swap(u, v);
        op.emplace_back(dfn[u], dfn[v]);
        return (op);
    }
    template <class F>
    void processP2P(int u, int v, F f) {
        // F: void(int L, int R) refers to the process of internal [L,R]
        while (top[u] != top[v]) {
            if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
            f(dfn[top[u]], dfn[u]);
            u = par[top[u]];
        }
        if (dep[u] > dep[v]) std::swap(u, v);
        f(dfn[u], dfn[v]);
    }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    BlockCutTree bct(G);

    HLD hld(bct.aux);

    hld.build();

    int Q;
    std::cin >> Q;

    while (Q--) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;

        if (x == y) {
            std::cout << 0 << '\n';
            continue;
        }

        int ans = hld.dep[bct.id(x)];
        ans += hld.dep[bct.id(y)];
        ans -= hld.dep[hld.lca(bct.id(x), bct.id(y))] * 2;
        ans -= bct.ar[x];
        ans -= bct.ar[y];

        ans /= 2;

        std::cout << ans << '\n';
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード