結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー betrue12
提出日時 2020-01-31 21:31:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 1,256 bytes
コンパイル時間 2,892 ms
コンパイル使用メモリ 196,092 KB
最終ジャッジ日時 2025-01-08 20:50:51
ジャッジサーバーID
(参考情報)
judge2 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> par;
vector<int> sz;
UnionFind(int n=0){
if(n>0) initialize(n);
}
void initialize(int n){
par.resize(n);
sz.resize(n);
for(int i=0; i<n; i++){
par[i] = i;
sz[i] = 1;
}
}
int find(int x){
if(par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
bool unite(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(sz[x] > sz[y]) swap(x, y);
par[x] = y;
sz[y] += sz[x];
return true;
}
bool same(int x, int y){
return find(x) == find(y);
}
int size(int x){
return sz[find(x)];
}
};
int main(){
int N;
cin >> N;
UnionFind uf(N);
vector<int> deg(N);
for(int i=0; i<N-1; i++){
int a, b;
cin >> a >> b;
deg[a]++;
deg[b]++;
uf.unite(a, b);
}
int cmp = 0, one = 0;
for(int i=0; i<N; i++){
if(uf.find(i) == i) cmp++;
if(deg[i] == 1) one++;
}
if(one) cmp++;
cout << (cmp >= 3 ? "Alice" : "Bob") << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0