結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー |
|
提出日時 | 2021-07-05 15:48:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,103 bytes |
コンパイル時間 | 3,154 ms |
コンパイル使用メモリ | 198,148 KB |
最終ジャッジ日時 | 2025-01-22 17:45:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 13 WA * 13 |
ソースコード
#define _USE_MATH_DEFINES#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define MT make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define RT returnusing ll = long long;using pii = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;class UnionFindBySize {int cnt;vector<int> par, size;public:UnionFindBySize() :cnt(0) {}UnionFindBySize(int _n) :cnt(_n), par(_n), size(_n, 1) {for (int i = 0; i < _n; ++i) par[i] = i;}int find(int k) {return (k == par[k]) ? k : (par[k] = find(par[k]));}int operator[](int k) {return find(k);}int getSize(int k) {return size[find(k)];}void unite(int x, int y) {x = find(x); y = find(y);if (x == y) return;--cnt;if (size[x] < size[y]) {par[x] = y;size[y] += size[x];} else {par[y] = x;size[x] += size[y];}}int count() {return cnt;}};void solve() {int N;cin >> N;UnionFindBySize UF(N);vi A(N); // ループはあるかrep(i, N - 1) {int u, v;cin >> u >> v;u = UF[u];v = UF[v];if (UF.getSize(u) < UF.getSize(v))swap(u, v);if (u == v) {A[u] = 1;} else {UF.unite(u, v);A[u] |= A[v];}}if (UF.count() > 1) {rep(i, N) {int u = UF[i];if (UF.getSize(u) > 1 && !A[u]) {cout << "Alice" << endl;return;}}}cout << "Bob" << endl;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);solve();return 0;}