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

提出ソース

結果

問題	No.1326 ふたりのDominator
ユーザー	yuri3
提出日時	2023-06-27 04:39:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,659 bytes
コンパイル時間	2,715 ms
コンパイル使用メモリ	223,780 KB
実行使用メモリ	29,520 KB
最終ジャッジ日時	2024-07-03 23:08:52
合計ジャッジ時間	4,878 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	3 ms 5,376 KB
testcase_12	AC	85 ms 18,400 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	83 ms 26,636 KB
testcase_21	AC	85 ms 26,692 KB
testcase_22	WA	-
testcase_23	AC	63 ms 16,932 KB
testcase_24	AC	88 ms 18,396 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

using i64 = std::int64_t;
using namespace std;
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;
                        curBcc.push_back(u);
                        while (st.top() != u) {
                            int curNode = st.top();
                            st.pop();
                            curBcc.push_back(curNode);
                        }
                        bcc.push_back(curBcc);
                    }
                } else if (dfn[v] < dfn[u])
                    low[u] = std::min(low[u], dfn[v]);
            }
            if (fa < 0 && childCnt == 1) 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]);
    }
};

template <typename G>
struct HeavyLightDecomposition {
   private:
    void dfs_sz(int cur) {
        size[cur] = 1;
        for (auto& dst : g[cur]) {
            if (dst == par[cur]) {
                if (g[cur].size() >= 2 && int(dst) == int(g[cur][0]))
                    swap(g[cur][0], g[cur][1]);
                else
                    continue;
            }
            depth[dst] = depth[cur] + 1;
            par[dst] = cur;
            dfs_sz(dst);
            size[cur] += size[dst];
            if (size[dst] > size[g[cur][0]]) {
                swap(dst, g[cur][0]);
            }
        }
    }

    void dfs_hld(int cur) {
        down[cur] = id++;
        for (auto dst : g[cur]) {
            if (dst == par[cur]) continue;
            nxt[dst] = (int(dst) == int(g[cur][0]) ? nxt[cur] : int(dst));
            dfs_hld(dst);
        }
        up[cur] = id;
    }

    // [u, v)
    vector<pair<int, int>> ascend(int u, int v) const {
        vector<pair<int, int>> res;
        while (nxt[u] != nxt[v]) {
            res.emplace_back(down[u], down[nxt[u]]);
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(down[u], down[v] + 1);
        return res;
    }

    // (u, v]
    vector<pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
        auto res = descend(u, par[nxt[v]]);
        res.emplace_back(down[nxt[v]], down[v]);
        return res;
    }

   public:
    G& g;
    int id;
    vector<int> size, depth, down, up, nxt, par;
    HeavyLightDecomposition(G& _g, int root = 0)
        : g(_g),
          id(0),
          size(g.size(), 0),
          depth(g.size(), 0),
          down(g.size(), -1),
          up(g.size(), -1),
          nxt(g.size(), root),
          par(g.size(), root) {
        dfs_sz(root);
        dfs_hld(root);
    }

    void build(int root) {
        dfs_sz(root);
        dfs_hld(root);
    }

    pair<int, int> idx(int i) const { return make_pair(down[i], up[i]); }

    template <typename F>
    void path_query(int u, int v, bool vertex, const F& f) {
        int l = lca(u, v);
        for (auto&& [a, b] : ascend(u, l)) {
            int s = a + 1, t = b;
            s > t ? f(t, s) : f(s, t);
        }
        if (vertex) f(down[l], down[l] + 1);
        for (auto&& [a, b] : descend(l, v)) {
            int s = a, t = b + 1;
            s > t ? f(t, s) : f(s, t);
        }
    }

    template <typename F>
    void path_noncommutative_query(int u, int v, bool vertex, const F& f) {
        int l = lca(u, v);
        for (auto&& [a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(down[l], down[l] + 1);
        for (auto&& [a, b] : descend(l, v)) f(a, b + 1);
    }

    template <typename F>
    void subtree_query(int u, bool vertex, const F& f) {
        f(down[u] + int(!vertex), up[u]);
    }

    int lca(int a, int b) {
        while (nxt[a] != nxt[b]) {
            if (down[a] < down[b]) swap(a, b);
            a = par[nxt[a]];
        }
        return depth[a] < depth[b] ? a : b;
    }

    int dist(int a, int b) {
        return depth[a] + depth[b] - depth[lca(a, b)] * 2;
    }
};
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);

    HeavyLightDecomposition 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.depth[bct.id(x)] + 1;
        ans += (hld.depth[bct.id(y)] + 1);
        ans -= hld.depth[hld.lca(bct.id(x), bct.id(y))] * 2 + 2;
        ans -= bct.is_arti(x);
        ans -= bct.is_arti(y);

        ans /= 2;

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

yukicoder

結果

テストケース

ソースコード