結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー kkk
提出日時 2024-12-01 21:41:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 2,289 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 91,132 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-12-01 21:41:19
合計ジャッジ時間 2,754 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define rep(i, S, E) for(int i=(S); i<=(E); i++)

struct Low_Link{
    
    vector<bool> seen;
    vector<int> ord, low;
    
    vector<pair<int, int>> E;
    vector<vector<int>> G;
    
    int order = 0;
    
    Low_Link(){ ; }
    Low_Link(int n){
        seen.resize(n, false);
        ord.reserve(n);
        low.reserve(n);
        
        E.reserve(n);
        G.reserve(n);
    }
    
    void set_graph(int x, int y){
        G[x].emplace_back(y);
        G[y].emplace_back(x);
        E.emplace_back(make_pair(x, y));
    }
    
    void execute(int s){
        order = 0;
        dfs(s, s, order);
    }
    
    void dfs(int v, int v_p, int& o){
        
        seen[v] = true;
        ord[v] = low[v] = o;
        o++;
        
        for (auto next : G[v]){
            if (!seen[next]){
                dfs(next, v, o);
                if (low[next] < low[v]){
                    low[v] = low[next];
                }
                
            }else{
                if (ord[next] < low[v] && next != v_p){
                    low[v] = ord[next];
                }
            }
        }
        
        return;
    }
    
    int count(void){
        int bridges = 0;
        
        for (auto e : E){
            int u, v;
            if (ord[e.first] < ord[e.second]){
                u = e.first;
                v = e.second;
            }else{
                v = e.first;
                u = e.second;
            }
            
            if (ord[u] < low[v]){
                bridges++;
            }
        }
        
        return bridges;
    }
    
};

int main() {
    
    int N;
    cin >> N;
    Low_Link ll(N);
    
    int x, y;
    int cnt[N];
    rep(i, 0, N-1){
        cnt[i] = 0;
    }
    
    
    rep(i, 0, N-2){
        cin >> x >> y;
        cnt[x]++;
        cnt[y]++;
        ll.set_graph(x, y);
    }
    
    int groups = 0;
    rep(i, 0, N-1){
        if (!ll.seen[i]){
            groups++;
            ll.execute(i);
        }
    }
    
    int bridges = ll.count();
    if (groups == 1 || (groups == 2 && bridges == 0)){
        cout << "Bob" << endl;
    }else{
        cout << "Alice" << endl;
    }
    
    return 0;
}
0