#1150503 (C++23) No.3463 Beltway

• 問題: No.3463 Beltway
• ユーザー: wasd314
• 提出日時: 2026-02-28 15:30:30
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 4,111 bytes
• コンパイル時間: 2,699 ms
• コンパイル使用メモリ: 210,656 KB
• 実行使用メモリ: 53,308 KB
• 最終ジャッジ日時: 2026-02-28 15:53:29
• 合計ジャッジ時間: 7,067 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 6 WA * 2 RE * 9

ソースコード

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor
を求める構造体 query(u,v): u と v の LCA を求める。計算量 O(logn) 前処理:
O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
    using Graph = std::vector<std::vector<int>>;
    std::vector<std::vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    std::vector<int> dist;  // root からの距離
    LCA(const Graph &G, int root = 0) { init(G, root); }

    // 初期化
    void init(const Graph &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, std::vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e != p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) std::swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int operator()(int x, int y) { return query(x, y); }
};
int solve() {
    using namespace std;
    int n, m, sv, gv;
    cin >> n >> m >> sv >> gv;
    sv--;
    gv--;
    using P = pair<int, int>;
    vector<P> edges(m);
    for (auto &e : edges) cin >> e.first >> e.second, e.first--, e.second--;
    const int oo = 1001001001;
    vector g1(n, vector<P>());
    vector g2(n, vector<int>());
    for (int i : views::iota(0, n)) {
        auto [x, y] = edges[i];
        g1[x].emplace_back(y, i);
        g1[y].emplace_back(x, i);
    }
    queue<int> q1;
    q1.push(sv);
    vector dist(n, oo);
    dist[sv] = 0;
    vector par(n, -1);
    vector pari(n, -1);
    while (!q1.empty()) {
        int v = q1.front();
        q1.pop();
        int nd = dist[v] + 1;
        for (auto [nv, i] : g1[v]) {
            if (dist[nv] > nd) {
                dist[nv] = nd;
                par[nv] = v;
                pari[nv] = i;
                g2[v].push_back(nv);
                g2[nv].push_back(v);
                q1.push(nv);
            }
        }
    }
    if (dist[gv] > oo / 2) {
        return -1;
    }
    LCA lca(g2, sv);
    vector<int> cy(n);
    vector mcy(m, 0);
    for (int i : views::iota(0, m)) {
        auto [x, y] = edges[i];
        if (pari[x] == i || pari[y] == i) continue;
        int l = lca(x, y);
        cy[x]++;
        cy[y]++;
        cy[l] -= 2;
        mcy[i] = 1;
    }
    auto dfs = [&](this auto self, int v, int p = -1) -> void {
        for (int nv : g2[v]) {
            if (nv == p) continue;
            self(nv, v);
            cy[v] += cy[nv];
        }
    };
    dfs(sv);
    for (int v : views::iota(0, n)) {
        if (v == sv) continue;
        mcy[pari[v]] = cy[v] >= 1;
    }
    vector dp(n, -oo);
    dp[sv] = 0;
    q1.push(sv);
    while (!q1.empty()) {
        int v = q1.front();
        q1.pop();
        for (auto [nv, i] : g1[v]) {
            if (dist[nv] != dist[v] + 1) continue;
            if (dp[nv] < 0) q1.push(nv);
            dp[nv] = max(dp[nv], dp[v] + mcy[i]);
        }
    }
    return dp[gv];
}
int main() {
    int ans = solve();
    std::cout << ans << "\n";
}