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

提出ソース

結果

問題	No.1326 ふたりのDominator
ユーザー	Felerius
提出日時	2021-06-01 19:26:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	121 ms / 2,000 ms
コード長	7,764 bytes
コンパイル時間	3,035 ms
コンパイル使用メモリ	237,716 KB
実行使用メモリ	25,892 KB
最終ジャッジ日時	2023-10-24 10:41:05
合計ジャッジ時間	5,708 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	3 ms 4,348 KB
testcase_08	AC	3 ms 4,348 KB
testcase_09	AC	3 ms 4,348 KB
testcase_10	AC	3 ms 4,348 KB
testcase_11	AC	3 ms 4,348 KB
testcase_12	AC	81 ms 16,932 KB
testcase_13	AC	82 ms 16,928 KB
testcase_14	AC	81 ms 16,936 KB
testcase_15	AC	83 ms 16,720 KB
testcase_16	AC	84 ms 16,392 KB
testcase_17	AC	76 ms 13,372 KB
testcase_18	AC	77 ms 11,924 KB
testcase_19	AC	57 ms 13,336 KB
testcase_20	AC	83 ms 24,040 KB
testcase_21	AC	97 ms 24,080 KB
testcase_22	AC	121 ms 25,892 KB
testcase_23	AC	64 ms 13,172 KB
testcase_24	AC	88 ms 16,928 KB

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

ソースコード

raw source code

#pragma GCC optimize("fast-math")
// begin "cp-lib/boilerplate.hpp"
#include <bits/stdc++.h>

#define _choose(_1, _2, _3, chosen, ...) chosen
#define _rep(i, l, r)     for (int i = l; i < r; ++i)
#define _rep0(i, r)       _rep(i, 0, r)
#define _repr(i, r, l)    for (int i = r; i >= l; --i)
#define _repr0(i, r)      _repr(i, r, 0)
#define rep(...)          _choose(__VA_ARGS__, _rep, _rep0, suppress_warning)(__VA_ARGS__)
#define repr(...)         _choose(__VA_ARGS__, _repr, _repr0, suppress_warning)(__VA_ARGS__)
#define all(a)            ::begin(a),::end(a)
#define trav(a, b)        for (auto&& a : b)

using namespace std;
namespace cp_lib {}

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using u32 = uint32_t;

[[maybe_unused]] static constexpr int INF = int(1e9 + 5);
[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;
[[maybe_unused]] static mt19937 rng(u32(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()));
template <class C> int sz(const C& c) { return int(::size(c)); }
// end "cp-lib/boilerplate.hpp"
// begin "cp-lib/graph/block-cut-tree.hpp"
// begin "_detail.hpp"
namespace cp_lib {
    struct Identity {
        template <class T> constexpr T&& operator()(T&& t) const noexcept { return forward<T>(t); }
    };

    template <class A, class M>
    struct Graph {
        const A& adj;
        int n;
        M map;

        Graph(const A& adj_, int n_, M&& map_) : adj{adj_}, n{n_}, map{forward<M>(map_)} {}
        Graph(const A& adj_, M&& map_) : adj{adj_}, n{sz(adj)}, map{forward<M>(map_)} {}
        Graph(const A& adj_, int n_) : adj{adj_}, n{n_}, map{Identity{}} {}
        explicit Graph(const A& adj_) : adj{adj_}, n{sz(adj)}, map{Identity{}} {}
    };

    template <class A> Graph(const A&, int) -> Graph<A, Identity>;
    template <class A> Graph(const A&) -> Graph<A, Identity>;
}
// end "_detail.hpp"

namespace cp_lib {
    struct BlockCutTree {
        vector<int> node;
        vector<bool> is_cut;
        vector<vector<int>> tree;

        template <class G>
        explicit BlockCutTree(G&& graph) {
            auto [adj, n, to] = Graph(forward<G>(graph));
            vector<int> idx = node = vector(n, -1), stack;
            is_cut = vector(n, false);

            auto make_component = [&](int rem) {
                int vt = sz(tree);
                tree.emplace_back();
                while (sz(stack) > rem) {
                    int v = stack.back(); stack.pop_back();
                    if (!is_cut[v])
                        node[v] = vt;
                    else if (!sz(tree[node[v]]) || tree[node[v]].back() != vt)
                        tree[vt].push_back(node[v]), tree[node[v]].push_back(vt);
                }
            };

            auto dfs = [&, &adj=adj, &to=to](int v, int p, int8_t root, auto&& self) -> int {
                int up = idx[v] = sz(stack);
                trav(e, adj[v]) {
                    int v2 = to(e);
                    if (v2 == p) continue;
                    if (idx[v2] == -1 || idx[v2] < idx[v])
                        stack.push_back(v), stack.push_back(v2);
                    if (idx[v2] != -1) { up = min(up, idx[v2]); continue; }

                    int up2 = self(v2, v, 0, self);
                    up = min(up, up2);
                    if (up2 >= idx[v]) {
                        if (root == 2) { --root; continue; }
                        if (!is_cut[v])
                            is_cut[v] = true, node[v] = sz(tree), tree.emplace_back();
                        make_component(idx[v2] - 2);
                        if (root == 1)
                            --root, make_component(0);
                    }
                }
                return up;
            };

            rep(i, n) {
                if (idx[i] != -1) continue;
                dfs(i, -1, 2, dfs);
                if (sz(stack)) make_component(0);
                if (node[i] == -1)
                    node[i] = sz(tree), tree.emplace_back();
            }
        }
    };
}
// end "cp-lib/graph/block-cut-tree.hpp"
// begin "cp-lib/graph/lca.hpp"
// begin "../ds/rmq.hpp"
// begin "../bit.hpp"
namespace cp_lib {
    template <class T> constexpr inline bool is_pow2(T n) { return n && !(n & (n - 1)); }
    template <class T> constexpr inline int floor_log2(T n) { return n ? 63 - __builtin_clzll(n) : 0; }
    template <class T> constexpr inline int ceil_log2(T n) { return floor_log2(n) + !is_pow2(n); }
}
// end "../bit.hpp"

namespace cp_lib {
    namespace _rmq_detail {
        template <class T, bool Max> T minmax(T a, T b) { return (a < b) ^ Max ? a : b; }
    }

    template <class T, T (*Combine)(T, T)>
    struct SparseTable {
        vector<vector<T>> d = {};

        SparseTable() = default;
        explicit SparseTable(const vector<T>& v) {
            int n = sz(v), k = floor_log2(n);
            d.assign(k + 1, v);
            rep(i, k) rep(j, n)
                d[i + 1][j] = Combine(d[i][j], d[i][min(j + (1 << i), n - 1)]);
        }

        // Aggregate for [l, r)
        T query(int l, int r) const {
            int k = floor_log2(r - l);
            return Combine(d[k][l], d[k][r - (1 << k)]);
        }
    };

    template <class T>
    using Rmq = SparseTable<T, _rmq_detail::minmax<T, false>>;
    template <class T>
    using Rmaxq = SparseTable<T, _rmq_detail::minmax<T, true>>;
}
// end "../ds/rmq.hpp"

namespace cp_lib {
    struct LowestCommonAncestor {
        vector<int> time, euler;
        Rmq<int> rmq;

        template <class G>
        LowestCommonAncestor(G&& graph, int root = 0) {
            auto [adj, n, to] = Graph(forward<G>(graph));
            if (!n) return;
            time = vector(n, -1);
            vector<int> d;
            auto dfs = [&, t=1, &adj=adj, &to=to](int v, int p, int tp, auto&& self) mutable -> void {
                euler.push_back(p);
                d.push_back(tp);
                time[v] = t++;
                trav(e, adj[v])
                    if (to(e) != p)
                        self(to(e), v, time[v], self);
            };
            dfs(root, -1, 0, dfs);
            rep(i, n)
                if (time[i] == -1)
                    dfs(i, -1, 0, dfs);
            rmq = Rmq<int>(d);
        }

        int lca(int u, int v) const {
            if (u == v) return u;
            auto [l, r] = minmax(time[u], time[v]);
            return euler[rmq.query(l, r)];
        }

        bool on_path(int v, pair<int, int> path) const {
            auto [a, b] = path;
            auto av = lca(a, v), bv = lca(b, v), ab = lca(a, b);
            return av != -1 && bv != -1 && ab != -1 && minmax(av, bv) == minmax(v, ab);
        }

        bool is_ancestor(int u, int v) const { return lca(u, v) == u; }
    };
}
// end "cp-lib/graph/lca.hpp"

#define PROBLEM "https://yukicoder.me/problems/no/1326"

using namespace cp_lib;

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, m; cin >> n >> m;
    vector adj(n, vector<int>());
    rep(_, m) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    BlockCutTree bct(adj);
    int nt = sz(bct.tree);
    LowestCommonAncestor lca(bct.tree);
    vector depth(nt, 0);
    auto dfs = [&](int v, int p, auto&& self) -> void {
        trav(v2, bct.tree[v])
            if (v2 != p)
                depth[v2] = depth[v] + 1, self(v2, v, self);
    };
    dfs(0, -1, dfs);

    int q; cin >> q;
    while (q--) {
        int u, v; cin >> u >> v; --u, --v;
        int tu = bct.node[u], tv = bct.node[v];
        int l = depth[tu] + depth[tv] - 2 * depth[lca.lca(tu, tv)];
        l -= bct.is_cut[u] + bct.is_cut[v];
        cout << max(0, l / 2) << '\n';
    }
}