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

• 問題: No.977 アリス仕掛けの摩天楼
• ユーザー: yudedako
• 提出日時: 2020-08-27 17:57:28
• 言語: C++11 (gcc 11.4.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	9 ms; 5,248 KB
testcase_14	AC	9 ms; 5,248 KB
testcase_15	AC	9 ms; 5,248 KB
testcase_16	AC	9 ms; 5,248 KB
testcase_17	AC	9 ms; 5,248 KB
testcase_18	AC	25 ms; 5,248 KB
testcase_19	AC	28 ms; 8,192 KB
testcase_20	AC	43 ms; 7,296 KB
testcase_21	AC	69 ms; 7,808 KB
testcase_22	AC	87 ms; 9,344 KB
testcase_23	AC	95 ms; 9,600 KB
testcase_24	AC	92 ms; 9,472 KB
testcase_25	AC	90 ms; 9,344 KB

ソースコード

#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";
	}
}