結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー |
|
提出日時 | 2024-12-01 21:14:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,055 bytes |
コンパイル時間 | 1,421 ms |
コンパイル使用メモリ | 90,564 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-12-01 21:14:55 |
合計ジャッジ時間 | 3,280 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 2 |
ソースコード
#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);}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 (e.first < 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;rep(i, 0, N-1){cin >> x >> 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;}