結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー yudedako
提出日時 2020-08-27 17:57:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 1,607 bytes
コンパイル時間 1,240 ms
コンパイル使用メモリ 111,020 KB
実行使用メモリ 9,600 KB
最終ジャッジ日時 2024-11-07 21:39:57
合計ジャッジ時間 2,423 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>
#include <random>
#include <fstream>
#include <cfloat>
#include <complex>

void dfs(const int current, int prev, int &order, std::vector<int>& ord, std::vector<int>& low, const std::vector<std::vector<int>> &nodes) {
	low[current] = ord[current] = order++;
	for (const auto next : nodes[current]) {
		if (next == prev) continue;
		if (ord[next] >= 0) {
			low[current] = std::min(low[current], ord[next]);
		}
		else {
			dfs(next, current, order, ord, low, nodes);
			low[current] = std::min(low[current], low[next]);
		}
	}
}
int main() {
	int n; std::cin >> n;
	std::vector<std::vector<int>> islands(n);
	for (auto i = 1; i < n; ++i) {
		int u, v; std::cin >> u >> v;
		islands[u].push_back(v);
		islands[v].push_back(u);
	}
	int order{ 0 };
	std::vector<int> ord(n, -1), low(n, -1);
	int count{ 0 };
	for (auto i = 0; i < n; ++i) {
		if (ord[i] == -1) {
			dfs(i, -1, order, ord, low, islands);
			++count;
		}
	}
	if (count == 1) {
		std::cout << "Bob\n";
	}
	else if (count == 2) {
		for (auto i = 0; i < n; ++i) {
			for (const auto next : islands[i]) {
				if (ord[i] < low[next]) {
					++count;
				}
			}
		}
		std::cout << (count == 2 ? "Bob\n" : "Alice\n");
	}
	else {
		std::cout << "Alice\n";
	}
}
0