結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | hirono999 |
提出日時 | 2020-01-31 22:41:47 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,590 bytes |
コンパイル時間 | 1,517 ms |
コンパイル使用メモリ | 175,928 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-09-17 09:32:40 |
合計ジャッジ時間 | 2,581 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | WA | - |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 5 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,940 KB |
testcase_15 | AC | 5 ms
6,940 KB |
testcase_16 | AC | 5 ms
6,940 KB |
testcase_17 | AC | 4 ms
6,944 KB |
testcase_18 | AC | 11 ms
6,948 KB |
testcase_19 | WA | - |
testcase_20 | AC | 20 ms
7,296 KB |
testcase_21 | AC | 32 ms
9,856 KB |
testcase_22 | AC | 41 ms
11,520 KB |
testcase_23 | AC | 38 ms
11,776 KB |
testcase_24 | AC | 37 ms
11,648 KB |
testcase_25 | AC | 43 ms
11,776 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for(ll i=0; i<(n); ++i) #define rep1(i,n) for(ll i=1; i<=(n); ++i) #define repi(i,a,b) for(ll i=a; i<=(b); ++i) #define rrep(i,n) for(ll i=(n-1); i>=0; --i) #define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr) #define ALL(obj) (obj).begin(), (obj).end() #define RALL(obj) (obj).rbegin(), (obj).rend() #define pb push_back #define mp make_pair #define to_s to_string #define sz(v) (int)v.size() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) #define print(x) cout<<(x)<<'\n' #define debug(x) cout << #x << ": " << (x) << '\n' using namespace std; using ll = long long; using Edge = pair<ll,ll>; using Graph = vector<vector<Edge>>; typedef pair<ll,ll> P; struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa; ll MOD = 1e9 + 7; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return (a*b)/gcd(a,b);} ll devc(ll x, ll y){return 1 + (x-1)/y;} ll modpow(ll x, ll y, ll m) { if (y == 0) return 1; ll res = modpow(x, y / 2, m); return res * res % m * (y & 1 ? x : 1) % m; } ll modinv(ll x) { return modpow(x, MOD - 2, MOD); } struct UnionFind { vector<int> par; vector<int> rank; vector<int> num; UnionFind(int N) : par(N),rank(N),num(N) { for(int i = 0; i < N; i++){ par[i] = i; rank[i] = 0; num[i] = 1; } } void init(int N){ for(int i = 0; i < N; i++){ par[i] = i; rank[i] = 0; num[i] = 1; } } int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); } int ranker(int x){ x = root(x); return rank[x]; } int number(int x){ x = root(x); return num[x]; } void unite(int x, int y){ int rx = root(x); int ry = root(y); if ( rx == ry ) return; if ( rank[rx] < rank[ry] ){ par[rx] = ry; num[ry] += num[rx]; num[rx] = 0; } else { par[ry] = rx; num[rx] += num[ry]; num[ry] = 0; if ( rank[rx] == rank[ry] ) rank[rx]++; } } bool same(int x, int y){ return root(x) == root(y); } }; int main(){ ll N; cin >> N; Graph G(N); UnionFind UF(N); rep(_, N-1){ ll u, v; cin >> u >> v; G[u].pb({v,1}); G[v].pb({u,1}); UF.unite(u,v); } bool flag = true; rep(i,N) if(sz(G[i]) < 2) flag = false; if(flag) print("Bob"); else if(UF.number(0) == N) print("Bob"); else print("Alice"); return 0; }