結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー parukiparuki
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 return
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0