結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー hanaokaunderbarhanaokaunderbar
提出日時 2020-03-10 19:54:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,924 bytes
コンパイル時間 2,148 ms
コンパイル使用メモリ 190,664 KB
実行使用メモリ 12,672 KB
最終ジャッジ日時 2024-04-27 18:48:58
合計ジャッジ時間 3,472 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 7 ms
6,944 KB
testcase_14 AC 8 ms
6,940 KB
testcase_15 AC 7 ms
6,944 KB
testcase_16 AC 7 ms
6,944 KB
testcase_17 AC 9 ms
6,944 KB
testcase_18 AC 19 ms
6,944 KB
testcase_19 AC 28 ms
6,944 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 99 ms
12,672 KB
testcase_24 AC 68 ms
12,672 KB
testcase_25 AC 89 ms
12,672 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;

#define int long long
#define cint cpp_int
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) (((a)+(b)-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2
#define PI acos(-1.0)
#define SUM(v) accumulate((v).begin(),(v).end(), 0ll)
#define range(i,left,right) (left<=i && i<right)

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;
typedef priority_queue<int> PQi;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vout(Vs &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());} //vectorの同じ要素消す
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
int leng(int n){string s=to_string(n); return s.size();} //intの桁数
int digitsum(int n){int ret=0; while(n>0){ret+=n%10;n/=10;}return ret;} //桁和
int lesscount(int x,Vi &a){return lower_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx未満の数の個数
int orlesscount(int x,Vi &a){return upper_bound(a.begin(),a.end(),x)-a.begin();} //vector aにおけるx以下の数の個数
int morecount(int x,Vi &a){return a.size()-orlesscount(x,a);} //vector aにおけるxより大きい数の個数
int ormorecount(int x,Vi &a){return a.size()-lesscount(x,a);} //vector aにおけるx以上の数の個数
int count(int x,Vi &a) {return upper_bound(ALL(a),x)-lower_bound(ALL(a),x);} //vector aにおけるxの個数
Vi accum(Vi &v){Vi ret((v).size()+1);REP(i,0,(v).size()) ret[i+1]=ret[i]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

struct UnionFind {
    vector<int> data;
    vector<int> sizes;
    
    UnionFind(int n) : data(n) ,sizes(n, 1){
        for(int i = 0; i < n; i++) data[i] = i;
    }
    
    int root(int x) {
        if (data[x] == x) return x;
        return data[x] = root(data[x]);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (y < x) swap(x, y);
        data[y] = x;
        sizes[x] += sizes[y];
    }
    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    int treesize(int x) {
        return sizes[root(x)];
    }
    int size(){
    	set<int> st;
        REP(i,0,data.size()) st.insert(root(i));
    	return st.size();
    }
};

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);
    int n;
    cin>>n;
    Vi a(n-1),b(n-1);
    REP(i,0,n-1) cin>>a[i]>>b[i];

    bool ans=false;
    map<int,int> bridge;
    REP(i,0,n-1){
        bridge[a[i]]++;
        bridge[b[i]]++;
    }
    REP(i,0,n){
        if(bridge[i]!=0 && bridge[i]!=2){
            break;
        }
        if(i==n-1) ans=true;
    }

    UnionFind UF(n);
    REP(i,0,n-1){
        UF.unite(a[i],b[i]);
    }
    if(UF.size()==1) ans=true;

    if(ans) cout<<"Bob"<<endl;
    else cout<<"Alice"<<endl;
    return 0;
}
0