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

• 問題: No.1326 ふたりのDominator
• ユーザー: Felerius
• 提出日時: 2022-02-13 01:34:34
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 78 ms / 2,000 ms
• コード長: 14,622 bytes
• コンパイル時間: 4,753 ms
• コンパイル使用メモリ: 338,296 KB
• 実行使用メモリ: 29,744 KB
• 最終ジャッジ日時: 2024-09-23 03:06:28
• 合計ジャッジ時間: 6,965 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	3 ms; 6,940 KB
testcase_08	AC	3 ms; 6,944 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	3 ms; 6,944 KB
testcase_12	AC	59 ms; 21,060 KB
testcase_13	AC	59 ms; 20,932 KB
testcase_14	AC	56 ms; 20,944 KB
testcase_15	AC	60 ms; 21,000 KB
testcase_16	AC	56 ms; 20,744 KB
testcase_17	AC	57 ms; 20,076 KB
testcase_18	AC	62 ms; 20,300 KB
testcase_19	AC	53 ms; 22,776 KB
testcase_20	AC	67 ms; 27,256 KB
testcase_21	AC	69 ms; 27,316 KB
testcase_22	AC	78 ms; 29,744 KB
testcase_23	AC	48 ms; 21,212 KB
testcase_24	AC	55 ms; 20,932 KB

ソースコード

#pragma GCC optimize("fast-math")

#include <bits/stdc++.h>
#ifdef LOCAL
#  include <dbg.h>
#else
#  define dbg(...) do {} while (0)
#endif

#define cp_lib_4th(_1, _2, _3, x, ...)  x
#define cp_lib_rep(i, l, r)             for (int i = (l); (i) < (r); ++(i))
#define cp_lib_rep0(i, r)               cp_lib_rep(i, 0, r)
#define rep(...)                        cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__)
#define cp_lib_repr(i, r, l, ...)       for (int i = (r); (i) >= (l); --(i))
#define repr(...)                       cp_lib_repr(__VA_ARGS__, 0)
#define all(a)                          ::begin(a),::end(a)
#define trav(a, b)                      for (auto&& a : (b))

using namespace std;
using ll = long long;
using ld = long double;
[[maybe_unused]] static constexpr int INF = int(1e9 + 5);
[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;
template <class C> int sz(const C& c) { return int(::size(c)); }


#ifdef CP_LIB_DEBUG
#define cp_lib_assert(expr) \
    do { if (!(expr)) { \
        ::cerr << "assertion failed: " << #expr << " (" << __FILE__ << ':' << __LINE__ << ")\n"; \
        ::abort(); \
    } } while (0)
#else
#define cp_lib_assert(expr)
#endif


#if __cplusplus < 202002L
struct identity { template <class T> constexpr T&& operator()(T&& t) const noexcept { return forward<T>(t); }; };
#endif
#if __cpp_lib_remove_cvref < 201711L
template <class T> using remove_cvref_t = remove_cv_t<remove_reference_t<T>>;
#endif

namespace cp_lib_type_meta {
    struct NoOp { template <class... Args> constexpr void operator()(Args&&...) const noexcept {} };
    template <class T, class = void> constexpr bool is_tuple_like = false;
    template <class T> constexpr bool is_tuple_like<T, void_t<tuple_element_t<0, T>>> = true;
}


namespace cp_lib_modint { struct ModIntTag {}; }
#include <unistd.h>

namespace cp_lib_io {
    constexpr int BUF_SIZE = 1 << 20;
    constexpr array<array<char, 4>, 10'000> DIGITS = []{
        array<array<char, 4>, 10'000> digits{};
        for (int i = 3, d = 1; i >= 0; --i, d *= 10)
            rep(j, 10'000)
                digits[j][i] = char('0' + j / d % 10);
        return digits;
    }();
    array<char, BUF_SIZE> ibuf, obuf;
    char *iptr = data(ibuf), *iend = iptr, *optr = data(obuf);

    template <class T> constexpr bool is_std_array = false;
    template <class T, size_t I> constexpr bool is_std_array<array<T, I>> = true;

    void flush() {
        for (auto* p = begin(obuf); p != optr; p += write(STDOUT_FILENO, p, optr - p));
        optr = begin(obuf);
    }
    int _flush_atexit = []{ atexit(flush); return 0; }();

    void refill() {
        memmove(begin(ibuf), iptr, iend - iptr);
        iend -= iptr - begin(ibuf);
        iptr = begin(ibuf);
        iend += read(STDIN_FILENO, iend, end(ibuf) - 1 - iend);
        *iend = '\0';
    }

    template <class T, class T2 = remove_cvref_t<T>>
    void print(T&& val) {
        if (end(obuf) - optr < 64)
            flush();

        if constexpr (is_same_v<T2, char>)
            *optr++ = val;
        else if constexpr (is_same_v<T2, bool> || is_same_v<T2, vector<bool>::reference>)
            return print(int(val));
        else if constexpr (is_integral_v<T2> && is_signed_v<T2>) {
            if (val < 0)
                *optr++ = '-';
            using U = make_unsigned_t<T2>;
            return print(U(val < 0 ? -U(val) : U(val)));
        } else if constexpr (is_integral_v<T2> && is_unsigned_v<T2>) {
            T2 val2 = val;
            array<char, 64> tmp;
            char* tptr = end(tmp);
            while (val2 >= 10'000)
                tptr -= 4, memcpy(tptr, &DIGITS[val2 % 10'000][0], 4), val2 /= T2(10'000);
            int d = (val2 >= 100 ? (val2 >= 1000 ? 4 : 3) : (val2 >= 10 ? 2 : 1));
            memcpy(optr, &DIGITS[val2][4 - d], d);
            memcpy(optr + d, tptr, end(tmp) - tptr);
            optr += d + int(end(tmp) - tptr);
        } else if constexpr (is_floating_point_v<T2>)
            optr += sprintf(optr, "%.30Lf", (long double)val);
        else if constexpr (is_convertible_v<T, string_view>) {
            string_view sv(val);
            if (sz(sv) + 1 <= end(obuf) - optr)
                memcpy(optr, data(sv), sz(sv)), optr += sz(sv);
            else {
                flush();
                for (auto *p = data(sv), *pe = p + sz(sv); p != pe; p += write(STDOUT_FILENO, p, pe - p));
            }
        } else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T2>)
            return print(decltype(T2::mod())(val));
        else if constexpr (cp_lib_type_meta::is_tuple_like<T2> && !is_std_array<T2>)
            return apply([](auto&&... items) { (print(items), ...); }, forward<T>(val));
        else {
            trav(item, val)
                print(item);
            return;
        }
        *optr++ = ' ';
    }

    template <class T>
    void read(T& val) {
        auto skip_ws = [] {
            do {
                for (; iptr != iend && *iptr <= ' '; ++iptr);
                if (iend - iptr < 64)
                    refill();
            } while (*iptr <= ' ');
        };
        auto read_other = [&](auto other) {
            read(other);
            return other;
        };

        if constexpr (is_same_v<T, char>)
            skip_ws(), val = *iptr++;
        else if constexpr (is_same_v<T, bool> || is_same_v<T, vector<bool>::reference>) {
            val = bool(read_other(uint8_t()));
        } else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T>) {
            val = T(read_other(ll()));
        } else if constexpr (is_integral_v<T>) {
            skip_ws();
            if (is_signed_v<T> && *iptr == '-')
                ++iptr, val = T(-read_other(make_unsigned_t<T>()));
            else
                for (val = 0; iptr != iend && *iptr > ' '; val = T(10 * val + (*iptr++ & 15)));
        } else if constexpr (is_floating_point_v<T>)
            skip_ws(), val = T(strtold(iptr, &iptr));
        else if constexpr (is_same_v<T, string>) {
            skip_ws();
            val.clear();
            do {
                auto* after = find_if(iptr, iend, [](char c) { return c <= ' '; });
                val.append(iptr, after);
                if ((iptr = after) != iend)
                    break;
                refill();
            } while (iptr != iend);
        } else if constexpr (cp_lib_type_meta::is_tuple_like<T> && !is_std_array<T>)
            apply([](auto&... items) { (read(items), ...); }, val);
        else
            trav(item, val)
                read(item);
    }
}

using cp_lib_io::flush;

template <class... Args>
void print(Args&&... args) { (cp_lib_io::print(forward<Args>(args)), ...); }

template <class... Args>
void println(Args&&... args) {
    if (sizeof...(Args))
        (cp_lib_io::print(forward<Args>(args)), ...), *(cp_lib_io::optr - 1) = '\n';
    else
        print('\n'), --cp_lib_io::optr;
}

template <class... Args>
void read(Args&... args) { (cp_lib_io::read(args), ...); }



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 n ? floor_log2(n) + !is_pow2(n) : 0; }

namespace cp_lib_rmq {
    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, cp_lib_rmq::minmax<T, false>>;
template <class T>
using Rmaxq = SparseTable<T, cp_lib_rmq::minmax<T, true>>;


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(move(map_)) {}
    Graph(const A& adj_, M map_) : Graph(adj_, sz(adj_), move(map_)) {}
    Graph(const A& adj_, int n_) : Graph(adj_, n_, identity()) {}
    explicit Graph(const A& adj_) : Graph(adj_, identity()) {}
};

template <class A> Graph(const A&, int) -> Graph<A, identity>;
template <class A> Graph(const A&) -> Graph<A, identity>;

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

    template <class G, class = enable_if_t<!is_same_v<LowestCommonAncestor, remove_cvref_t<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; }
};

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

    using Mapped = decltype(declval<M>()(*begin(declval<A>()[0])));

    NewGraph(A& adj_, M map_) : adj(adj_), n(sz(adj)), map(move(map_)) {}
    explicit NewGraph(A& adj_) : NewGraph(adj_, identity()) {}
};

template <class A> NewGraph(A&) -> NewGraph<A, identity>;

template <class G, class OnComp>
void biconnected_components(G&& graph, OnComp&& on_comp) {
    auto [adj, n, map] = NewGraph(forward<G>(graph));
    auto normalize = [&](auto mapped) {
        if constexpr(is_convertible_v<int, decltype(mapped)>)
            return pair(int(mapped), 0);
        else
            return mapped;
    };
    vector idx(n, INF);
    vector<pair<int, decltype(begin(adj[0]))>> stack;

    auto dfs = [&, &adj = adj, &map = map](int v, pair<int, int> pe, auto&& self) -> int {
        int up = idx[v] = sz(stack), cnt = 0;
        for (auto it = begin(adj[v]); it != end(adj[v]); ++it) {
            auto [v2, e] = normalize(map(*it));
            if (pair(v2, e) == pe)
                continue;
            up = min(up, idx[v2]);
            if (idx[v2] == INF || idx[v2] < idx[v])
                stack.emplace_back(v, it);
            if (idx[v2] != INF)
                continue;

            int up2 = self(v2, pair(v, e), self);
            up = min(up, up2);
            if (up2 >= idx[v]) {
                auto cut_v = (pe.first == -1 && !cnt++ ? nullopt : optional(v));
                on_comp(cut_v, begin(stack) + idx[v2] - 1, end(stack));
                stack.resize(idx[v2] - 1);
            }
        }
        return up;
    };

    rep(i, n)
        if (idx[i] == INF)
            dfs(i, pair(-1, 0), dfs);
}

template <class G>
vector<vector<int>> block_vertex_tree(G&& graph) {
    NewGraph g(forward<G>(graph));
    vector adj(g.n, vector<int>());
    biconnected_components(g, [&](auto, auto it, auto it_end) {
        int vc = sz(adj);
        adj.emplace_back();
        for (; it != it_end; ++it)
            for (int v : {it->first, g.map(*it->second)})
                if (!sz(adj[v]) || adj[v].back() != vc)
                    adj[v].push_back(vc), adj[vc].push_back(v);
    });
    return adj;
}

int main() {
    // int n, m; read(n, m);
    // vector adj(n, vector<pair<int, int>>());
    // rep(i, m) {
    //     int u, v; read(u, v);
    //     adj[u].emplace_back(v, i);
    //     adj[v].emplace_back(u, i);
    // }

    // vector<vector<int>> bicomps;
    // biconnected_components(adj, [&](auto, auto it, auto it_end) {
    //     auto& comp = bicomps.emplace_back();
    //     for (; it != it_end; ++it)
    //         comp.push_back(it->second->second);
    // });

    // println(sz(bicomps));
    // trav(comp, bicomps)
    //     println(sz(comp), comp);


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

    // set<int> cut_vertices;
    // biconnected_components(adj, [&](auto cut_v, auto, auto) {
    //     if (cut_v)
    //         cut_vertices.emplace(*cut_v);
    // });

    // trav(v, cut_vertices)
    //     println(v);


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

    // auto bvt = block_vertex_tree(adj);
    // int nt = sz(bvt);
    // vector wsum(nt, 0ll);
    // copy(all(w), begin(wsum));
    // auto dfs = [&](int v, int p, auto&& self) -> void {
    //     trav(v2, bvt[v])
    //         if (v2 != p)
    //             self(v2, v, self), wsum[v] += wsum[v2];
    // };
    // dfs(0, -1, dfs);

    // rep(i, n) {
    //     if (sz(bvt[i]) == 1) {
    //         println(wsum[0] - w[i]);
    //         continue;
    //     }

    //     ll mx = wsum[0] - wsum[i];
    //     trav(v, bvt[i])
    //         if (wsum[v] < wsum[i])
    //             mx = max(mx, wsum[v]);
    //     println(mx);
    // }


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

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

    int q; read(q);
    while (q--) {
        int u, v; read(u, v); --u, --v;
        int d = depth[u] + depth[v] - 2 * depth[lca.lca(u, v)];
        println(u == v ? 0 : (d - 2) / 2);
    }
}