結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | Y17 |
提出日時 | 2020-01-31 21:43:04 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 1,136 bytes |
コンパイル時間 | 2,002 ms |
コンパイル使用メモリ | 168,188 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-17 07:32:38 |
合計ジャッジ時間 | 3,449 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct UnionFind{ vector<int> tree; UnionFind(int n): tree(n+1, -1) {}; int root(int i){ return tree[i] < 0 ? i : tree[i] = root(tree[i]); } bool unite(int i, int j){ i = root(i), j = root(j); if(i == j) return false; tree[i] += tree[j], tree[j] = i; return true; } bool same(int i, int j){ return root(i) == root(j); } int size(int i){ return -tree[root(i)]; } }; int main(){ int n; cin >> n; UnionFind uf(n); int cnt[100010]; for(int i = 0;i < n-1;i++){ int a, b; cin >> a >> b; cnt[a]++; cnt[b]++; uf.unite(a, b); } map<int, int> mp; for(int i = 0;i < n;i++){ mp[uf.root(i)]++; } if(mp.size() > 2){ cout << "Alice" << endl; }else if(mp.size() == 1){ cout << "Bob" << endl; }else{ for(int i = 0;i < n;i++){ if(!(cnt[i] == 2 || cnt[i] == 0)){ cout << "Alice" << endl; return 0; } } cout << "Bob" << endl; } return 0; }