結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー kkkkkk
提出日時 2024-12-01 21:20:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,065 bytes
コンパイル時間 1,191 ms
コンパイル使用メモリ 90,952 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-12-01 21:20:25
合計ジャッジ時間 3,416 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 WA -
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 9 ms
5,248 KB
testcase_14 AC 9 ms
5,248 KB
testcase_15 AC 9 ms
5,248 KB
testcase_16 AC 9 ms
5,248 KB
testcase_17 AC 11 ms
5,248 KB
testcase_18 AC 25 ms
5,376 KB
testcase_19 WA -
testcase_20 AC 45 ms
7,552 KB
testcase_21 AC 79 ms
8,576 KB
testcase_22 AC 94 ms
10,112 KB
testcase_23 AC 98 ms
10,368 KB
testcase_24 AC 98 ms
10,368 KB
testcase_25 AC 102 ms
10,368 KB
権限があれば一括ダウンロードができます

ソースコード

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);
            }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;
    rep(i, 0, N-1){
        cin >> x >> 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