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

提出ソース

結果

問題	No.1326 ふたりのDominator
ユーザー	Felerius
提出日時	2021-05-25 18:41:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	121 ms / 2,000 ms
コード長	7,973 bytes
コンパイル時間	3,242 ms
コンパイル使用メモリ	237,652 KB
実行使用メモリ	25,784 KB
最終ジャッジ日時	2024-09-23 03:05:06
合計ジャッジ時間	5,636 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,812 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 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	3 ms 6,944 KB
testcase_11	AC	3 ms 6,940 KB
testcase_12	AC	84 ms 16,472 KB
testcase_13	AC	86 ms 16,648 KB
testcase_14	AC	85 ms 16,916 KB
testcase_15	AC	85 ms 16,360 KB
testcase_16	AC	82 ms 16,476 KB
testcase_17	AC	75 ms 13,296 KB
testcase_18	AC	79 ms 11,896 KB
testcase_19	AC	60 ms 13,200 KB
testcase_20	AC	85 ms 23,812 KB
testcase_21	AC	100 ms 23,980 KB
testcase_22	AC	121 ms 25,784 KB
testcase_23	AC	66 ms 13,168 KB
testcase_24	AC	88 ms 16,344 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/_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 "cp-lib/graph/_detail.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) {
            auto [adj, n, to] = Graph(forward<G>(graph));
            if (!n) return;
            time.resize(n);
            vector<int> d;
            int t = 0;
            auto dfs = [&, &adj=adj, &to=to](int v, int p, auto&& self) -> void {
                time[v] = t++;
                trav(e, adj[v])
                    if (to(e) != p)
                        euler.push_back(v), d.push_back(time[v]), self(to(e), v, self);
            };
            dfs(root, -1, 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;
            return minmax(lca(a, v), lca(b, v)) == minmax(v, lca(a, b));
        }
    };
}
// end "cp-lib/graph/lca.hpp"

using namespace cp_lib;

template <class G, class F>
void find_bridges(G&& graph, F&& f) {
    auto [adj, n, to] = Graph(forward<G>(graph));
    vector<int> idx(n, -1), stack;
    auto dfs = [&, &adj=adj, &to=to](int v, int p, auto&& self) -> int {
        int up = idx[v] = sz(stack);
        stack.push_back(v);
        for (auto it = begin(adj[v]), it_end = end(adj[v]); it != it_end; ++it) {
            int v2 = to(*it);
            if (v2 == p) { p = -1; continue; }
            int up2 = (idx[v2] == -1 ? self(v2, v, self) : idx[v2]);
            if (up2 > idx[v])
                f(v, it, begin(stack) + idx[v2], end(stack)), stack.resize(idx[v2]);
            up = min(up, up2);
        }
        return up;
    };

    rep(i, n) {
        if (idx[i] != -1) continue;
        dfs(i, -1, dfs);
        f(-1, end(adj[0]), all(stack));
        stack.clear();
    }
}

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);
        }
    }
};

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);
    LowestCommonAncestor lca(bct.tree, 0);
    vector depth(sz(bct.tree), -1);
    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);
    };
    rep(i, sz(bct.tree))
        if (depth[i] == -1)
            depth[i] = 0, dfs(i, -1, dfs);

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

yukicoder

結果

テストケース

ソースコード