結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー |
|
提出日時 | 2024-12-01 21:41:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 2,289 bytes |
コンパイル時間 | 1,012 ms |
コンパイル使用メモリ | 91,132 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-12-01 21:41:19 |
合計ジャッジ時間 | 2,754 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <vector>#include <math.h>#include <iostream>#include <algorithm>using namespace std;#define rep(i, S, E) for(int i=(S); i<=(E); i++)struct Low_Link{vector<bool> seen;vector<int> ord, low;vector<pair<int, int>> E;vector<vector<int>> G;int order = 0;Low_Link(){ ; }Low_Link(int n){seen.resize(n, false);ord.reserve(n);low.reserve(n);E.reserve(n);G.reserve(n);}void set_graph(int x, int y){G[x].emplace_back(y);G[y].emplace_back(x);E.emplace_back(make_pair(x, y));}void execute(int s){order = 0;dfs(s, s, order);}void dfs(int v, int v_p, int& o){seen[v] = true;ord[v] = low[v] = o;o++;for (auto next : G[v]){if (!seen[next]){dfs(next, v, o);if (low[next] < low[v]){low[v] = low[next];}}else{if (ord[next] < low[v] && next != v_p){low[v] = ord[next];}}}return;}int count(void){int bridges = 0;for (auto e : E){int u, v;if (ord[e.first] < ord[e.second]){u = e.first;v = e.second;}else{v = e.first;u = e.second;}if (ord[u] < low[v]){bridges++;}}return bridges;}};int main() {int N;cin >> N;Low_Link ll(N);int x, y;int cnt[N];rep(i, 0, N-1){cnt[i] = 0;}rep(i, 0, N-2){cin >> x >> y;cnt[x]++;cnt[y]++;ll.set_graph(x, y);}int groups = 0;rep(i, 0, N-1){if (!ll.seen[i]){groups++;ll.execute(i);}}int bridges = ll.count();if (groups == 1 || (groups == 2 && bridges == 0)){cout << "Bob" << endl;}else{cout << "Alice" << endl;}return 0;}