結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー kkkkkk
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0