結果

問題 No.3463 Beltway
コンテスト
ユーザー GOTKAKO
提出日時 2026-03-02 01:44:10
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 8,182 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,686 ms
コンパイル使用メモリ 265,216 KB
実行使用メモリ 78,900 KB
最終ジャッジ日時 2026-03-02 01:44:16
合計ジャッジ時間 4,700 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

class UnionFind{
    private:
    vector<int> par,siz;
    public:
    UnionFind(int N){
        par.resize(N,-1);
        siz.resize(N,1);
    }
 
    int root(int x){ //連結成分の代表頂点を返す.
        if(par.at(x) == -1) return x;
        else return par.at(x) = root(par.at(x));
    }
    bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す.
        u = root(u),v = root(v);
        if(u == v) return false;
 
        if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size.
        par.at(v) = u;
        siz.at(u) += siz.at(v);
        return true;
    }
    bool issame(int u, int v){ //同じ連結成分ならtrue.
        if(root(u) == root(v)) return true;
        else return false;
    }
    int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す.
};

vector<int> BFS(vector<vector<int>> &Graph,int start){
    int N = Graph.size();
    vector<int> ret(N,-1);
    queue<int> Q;
    ret.at(start) = 0,Q.push(start);
    while(Q.size()){
        int pos = Q.front(); Q.pop();
        for(auto to : Graph.at(pos)){
            if(ret.at(to) != -1) continue;
            ret.at(to) = ret.at(pos)+1;
            Q.push(to);
        }
    }
    return ret;
}

class SpecialSparseTable{ //LCA専用.
    private:
    int log = 0;
    pair<int,int> op(pair<int,int> &a,pair<int,int> &b){return min(a,b);}
    pair<int,int> add(pair<int,int> &a,pair<int,int> &b){return {a.first+b.first,a.second+b.second};}
    vector<int> check,belong,Second;
    vector<pair<int,int>> Add;
    vector<vector<vector<pair<int,int>>>> Group;
    vector<vector<pair<int,int>>> table;
    void maketable(vector<pair<int,int>> &A){
        int n = A.size();
        table.resize(n+1); check.resize(n+1);
        int p2 = 1;
        for(int i=1; i<=n; i++){
            if(i == p2) check.at(i) = i,p2 *= 2;
            else check.at(i) = check.at(i-1);
        }
        table.at(1) = A;
        for(int i=2; i<=n; i*=2){
            table.at(i).resize(n);
            for(int k=0; k<=n-i; k++) table[i][k] = op(table[i>>1][k],table[i>>1][k+(i>>1)]);
        }
    }
    void makeGroup(vector<pair<int,int>> &A){
        int loop = 1<<(log-1);
        Group.resize(loop,vector<vector<pair<int,int>>>(log,vector<pair<int,int>>(log)));
        for(int i=0; i<loop; i++){
            vector<int> now(1);
            for(int k=0; k<log-1; k++){
                if(i&(1<<k)) now.push_back(now.back()+1);
                else now.push_back(now.back()-1);
            }
            for(int l=0; l<log; l++){
                int mina = 1001001001,pos = -1;
                for(int r=l; r<log; r++){
                    if(mina > now.at(r)) mina = now.at(r),pos = r;
                    Group.at(i).at(l).at(r) = {mina,pos};
                }
            }
        }
    }
    pair<int,int> tablerange(int l,int r){//[L,R)だよ.
        int len = r-l,pos = check.at(len);
        return op(table.at(pos).at(l),table.at(pos).at(r-pos));
    }
    public:
    void make(vector<pair<int,int>> &A){
        int p2 = 1,n = A.size();
        while(p2 < n) p2 *= 2,log++;
        log = max(1,(log+1)/2);
 
        vector<pair<int,int>> sepa;
        for(int i=0; i<n; i+=log){
            int r = min(n,i+log),g = 0;
            pair<int,int> now = {1001001001,-1};
            for(int k=i; k<r; k++){
                if(k != r-1 && A.at(k).first+1 == A.at(k+1).first) g += (1<<(k-i));
                Second.push_back(A.at(k).second);
                if(now > A.at(k)) now = {A.at(k).first,k};
            }
            Add.push_back({A.at(i).first,i});
            sepa.push_back(now); belong.push_back(g);
        }
        maketable(sepa); makeGroup(A); 
    }
    int rangeans(int l,int r){ //[l,r)!
        int l2 = (l+log-1)/log,r2 = r/log;
        pair<int,int> mind = {1001001001,-1};
        if(l2 > r2) mind = add(Group[belong[r2]][l%log][(r-1)%log],Add[r2]);
        else{
            if(l2 < r2) mind = tablerange(l2,r2);
            if(l%log) mind = min(mind,add(Group[belong[l2-1]][l%log][log-1],Add[l2-1]));
            if(r%log) mind = min(mind,add(Group[belong[r2]][0][(r-1)%log],Add[r2]));
        }
        return Second.at(mind.second);
    }
};
class LCA{
    private:
    vector<int> dist,in,out;
    SpecialSparseTable ST;
    public:
    void make1(vector<int> &P){// p0=-1でp1以降だけ
        int r = 0;
        vector<vector<int>> G(P.size()+1);
        for(int i=0; i<P.size(); i++) G.at(P.at(i)).push_back(i+1); 
        make3(G,r);
    }
    void make2(vector<int> &P){//pi=-1 iは固定されていない.
        int r = -1;
        vector<vector<int>> G(P.size());
        for(int i=0; i<P.size(); i++){
            if(P.at(i) == -1) r = i;
            else G.at(P.at(i)).push_back(i);
        }
        make3(G,r);
    }
    void make3(vector<vector<int>> &Graph,int root){ //直接グラフを渡す.
        int t = 0,dep = 0,n = Graph.size(),pos = root;
        dist.resize(n),in.resize(n),out.resize(n);
 
        vector<pair<int,int>> depth;
        vector<int> Itr(n,-1),P(n,-1);
        while(pos != -1){
            depth.push_back({dep,pos});
            if(++Itr.at(pos) == 0) in.at(pos) = t;
            int to = P.at(pos);
            if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
            else{
                to = Graph.at(pos).at(Itr.at(pos));
                if(to == P.at(pos)){
                    Itr.at(pos)++;
                    if(Itr.at(pos) == Graph.at(pos).size()) out.at(pos) = ++t;
                    else to = Graph.at(pos).at(Itr.at(pos));
                }
            }
            if(to != P.at(pos)) dist.at(to) = dist.at(pos)+1,P.at(to) = pos,t++,dep++;
            else dep--;
            pos = to;
        }
        ST.make(depth);
    }
    int lca(int u,int v){
        int tu = in.at(u),tv = in.at(v);
        if(tu > tv) swap(tu,tv);
        return ST.rangeans(tu,tv+1);
    }
    int twodist(int u,int v){return dist.at(u)+dist.at(v)-2*dist.at(lca(u,v));}
    int onedist(int u){return dist.at(u);} 
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M,S,G; cin >> N >> M >> S >> G,S--,G--;
    vector<pair<int,int>> edge(M);
    vector<vector<int>> Graph(N);
    for(auto &[u,v] : edge){
        cin >> u >> v;
        u--; v--;
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }
    auto dist = BFS(Graph,S);
    if(dist.at(G) == -1){cout << "-1\n"; return 0;}
    vector<int> P(N,-1);
    int n = 0;
    for(int i=0; i<N; i++) if(dist.at(i) != -1) P.at(i) = n++;
    S = P.at(S),G = P.at(G);
    vector<pair<int,int>> left;
    UnionFind Z(n);
    Graph.assign(n,vector<int>(0));
    for(auto [u,v] : edge){
        if(P.at(u) == -1) continue;
        u = P.at(u),v = P.at(v);
        if(Z.unite(u,v)){
            Graph.at(u).push_back(v);
            Graph.at(v).push_back(u);
        }
        else left.push_back({u,v});
    }

    set<pair<int,int>> OK;
    LCA L; L.make3(Graph,S);
    vector<int> V(n);
    for(auto [u,v] : left){
        V.at(u)++,V.at(v)++;
        V.at(L.lca(u,v)) -= 2;
        OK.insert({u,v}),OK.insert({v,u});
    }
    auto dfs = [&](auto dfs,int pos,int back) -> int {
        int ret = V.at(pos);
        for(auto to : Graph.at(pos)){
            if(to == back) continue;
            int kid = dfs(dfs,to,pos);
            ret += kid;
            if(kid) OK.insert({pos,to}),OK.insert({to,pos});
        }
        return ret;
    };
    dfs(dfs,S,-1);
    for(auto [u,v] : left){
        Graph.at(u).push_back(v);
        Graph.at(v).push_back(u);
    }

    dist = BFS(Graph,S);
    vector<int> dp(n);
    queue<int> Q; Q.push(S);
    vector<bool> already(n);
    already.at(S) = true; 
    while(Q.size()){
        int pos = Q.front(); Q.pop();
        for(auto to : Graph.at(pos)) if(dist.at(to) == dist.at(pos)+1){
            if(OK.count({pos,to})) dp.at(to) = max(dp.at(to),dp.at(pos)+1);
            else dp.at(to) = max(dp.at(to),dp.at(pos));
            if(already.at(to)) continue;
            already.at(to) = true,Q.push(to);
        }    
    }

    cout << dp.at(G) << endl;
}
0