結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー otamay6
提出日時 2020-01-31 21:45:43
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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