結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー 東前頭十一枚目
提出日時 2020-02-01 04:52:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,158 bytes
コンパイル時間 1,683 ms
コンパイル使用メモリ 172,004 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 19:30:04
合計ジャッジ時間 3,128 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
	const int V;
	// par[x] := xのroot
	vector<int> par;
	// sz[x] := xを含む集合のサイズ
	vector<int> sz;
	UnionFind(const int V) :
		V(V),
		par(vector<int>(V)),
		sz(vector<int>(V, 1))
		{
			for(int i = 0; i < V; ++i) par[i] = i;
		}
	bool unite(int x, int y) {
		x = root(x), y = root(y);
		if(same(x, y)) return false;
		if(y < x) swap(x, y);
		par[y] = x;
		sz[x] += sz[y];
		return true;
	}
	int root(int x) {
		if(par[x] == x) return x;
		return (par[x] = root(par[x]));
	}
	bool same(int x, int y) {
		return (root(x) == root(y));
	}
	int size(int x) {
		return sz[root(x)];
	}
};


int main() {
	int n; cin >> n;
	UnionFind uf(n);
	int deg[n] = {};
	for(int i = 0; i < n - 1; ++i) {
		int u, v; cin >> u >> v;
		++deg[u];
		++deg[v];
		uf.unite(u, v);
	}
	int e = 0;
	for(int i = 0; i < n; ++i) {
		if(i == uf.root(i)) {
			++e;
		}
	}
	string ans;
	if(e == 1) {
		ans = "Bob";
	} else if(e >= 3) {
		ans = "Alice";
	} else {
		ans = "Bob";
		for(int i = 0; i < n; ++i) {
			if(deg[i] != 0 or deg[i] != 2) {
				ans = "Alice";
			}
		}
	}
	cout << ans << '\n';
	return 0;
}
0