#607554 (C++17) No.977 アリス仕掛けの摩天楼

• 問題: No.977 アリス仕掛けの摩天楼
• ユーザー: tkmst201
• 提出日時: 2021-01-20 10:45:03
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 27 ms / 2,000 ms
• コード長: 1,632 bytes
• コンパイル時間: 2,042 ms
• コンパイル使用メモリ: 204,152 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-01 11:23:00
• 合計ジャッジ時間: 3,230 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	4 ms; 5,376 KB
testcase_15	AC	4 ms; 5,376 KB
testcase_16	AC	4 ms; 5,376 KB
testcase_17	AC	4 ms; 5,376 KB
testcase_18	AC	8 ms; 5,376 KB
testcase_19	AC	9 ms; 5,376 KB
testcase_20	AC	14 ms; 5,376 KB
testcase_21	AC	21 ms; 5,376 KB
testcase_22	AC	26 ms; 5,376 KB
testcase_23	AC	27 ms; 5,376 KB
testcase_24	AC	27 ms; 5,376 KB
testcase_25	AC	27 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = false;
//---------------------------------//

struct UnionFind {
public:
	using size_type = std::size_t;
	
	UnionFind(size_type n) : n(n), size_(n, 1) {
		par.resize(n);
		std::iota(par.begin(), par.end(), 0);
	}
	
	size_type size(size_type x) { return size_[find(x)]; }
	
	size_type find(size_type x) {
		assert(x < n);
		while (par[x] != x) {
			par[x] = par[par[x]];
			x = par[x];
		}
		return x;
	}
	
	void unite(size_type x, size_type y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (size(x) > size(y)) std::swap(x, y);
		par[x] = y;
		size_[y] += size_[x];
	}
	
	bool issame(size_type x, size_type y) { return find(x) == find(y); }
	
private:
	size_type n;
	std::vector<size_type> size_, par;
};

int main() {
	int N;
	cin >> N;
	vector<int> cnt(N);
	UnionFind uf(N);
	REP(i, N - 1) {
		int u, v;
		scanf("%d %d", &u, &v);
		++cnt[u]; ++cnt[v];
		uf.unite(u, v);
	}
	
	int ccp = 0;
	REP(i, N) if (uf.find(i) == i) ++ccp;
	
	int two = 0;
	REP(i, N) if (cnt[i] == 2) ++two;
	if (ccp == 1 || ccp == 2 && two == N - 1) puts("Bob");
	else puts("Alice");
}