結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー otamay6otamay6
提出日時 2020-01-31 21:45:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 77 ms / 2,000 ms
コード長 2,528 bytes
コンパイル時間 1,599 ms
コンパイル使用メモリ 178,732 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-09-17 07:34:23
合計ジャッジ時間 2,899 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 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 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 8 ms
6,944 KB
testcase_14 AC 8 ms
6,940 KB
testcase_15 AC 7 ms
6,940 KB
testcase_16 AC 8 ms
6,944 KB
testcase_17 AC 8 ms
6,940 KB
testcase_18 AC 23 ms
6,944 KB
testcase_19 AC 23 ms
6,940 KB
testcase_20 AC 35 ms
6,940 KB
testcase_21 AC 55 ms
8,576 KB
testcase_22 AC 72 ms
9,984 KB
testcase_23 AC 76 ms
10,240 KB
testcase_24 AC 74 ms
10,368 KB
testcase_25 AC 77 ms
10,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;
class UnionFind{
 private:
    vector<int> Parent,es;
    vector<ll> diff_weight;
 public:
    UnionFind(int N){
        es.resize(N,0);
        Parent.resize(N,-1);
        diff_weight.resize(N,0LL);
    }

    int root(int A){
        if(Parent[A]<0) return A;
        else{ 
            int r = root(Parent[A]);
            diff_weight[A] += diff_weight[Parent[A]]; // 累積和をとる
            return Parent[A]=r;
        }
    }
    bool issame(int A,int B){
        return root(A)==root(B);
    }
    ll weight(int x) {
        root(x); // 経路圧縮
        return diff_weight[x];
    }
    ll diff(int x, int y) {
        return weight(y) - weight(x);
    }
    int size(int A){
        return -Parent[root(A)];
    }
    int eize(int A){
        return es[root(A)];
    }
    bool connect(int A,int B){
        A=root(A); B=root(B);
        if(A==B) return false;
        if(size(A)<size(B)) std::swap(A,B);
        Parent[A]+=Parent[B];
        es[A]+=es[B]+1;
        Parent[B]=A;
        return true;
    }
    void unite(int A,int B){
        A=root(A); B=root(B);
        if(A==B){ 
            es[A]++;
            return;
        }
        if(size(A)<size(B)) std::swap(A,B);
        Parent[A]+=Parent[B];
        es[A]+=es[B]+1;
        Parent[B]=A;
        return;
    }
    bool merge(int A, int B, ll w) {
        // x と y それぞれについて、 root との重み差分を補正
        w += weight(A); w -= weight(B); 
        A=root(A); B=root(B);
        if(A==B) return false;
        if(size(A)<size(B)) std::swap(A,B),w=-w;
        Parent[A]+=Parent[B];
        Parent[B]=A;
        // x が y の親になるので、x と y の差分を diff_weight[y] に記録
        diff_weight[B] = w; 
        return true;
    }
};
int main(){
    int N;cin>>N;
    UnionFind uni(N);
    vector<vector<int>> graph(N);
    REP(i,N-1){
        int a,b;cin>>a>>b;
        uni.connect(a,b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int ans=0,u=0;
    REP(i,N) if(!uni.issame(0,i)) ans++,u=i;
    if(ans==0) cout<<"Bob"<<endl;
    else if(ans==1){
        REP(i,N) if(graph[i].size()&1){
            cout<<"Alice"<<endl;
            return 0;
        }
        cout<<"Bob"<<endl;
    }
    else cout<<"Alice"<<endl;
}
0