結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | 👑 emthrm |
提出日時 | 2020-01-31 21:46:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 3,500 bytes |
コンパイル時間 | 2,477 ms |
コンパイル使用メモリ | 218,104 KB |
実行使用メモリ | 13,972 KB |
最終ジャッジ日時 | 2024-09-17 07:34:52 |
合計ジャッジ時間 | 3,249 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 6 ms
5,376 KB |
testcase_14 | AC | 5 ms
5,376 KB |
testcase_15 | AC | 5 ms
5,376 KB |
testcase_16 | AC | 6 ms
5,376 KB |
testcase_17 | AC | 7 ms
5,940 KB |
testcase_18 | AC | 15 ms
6,560 KB |
testcase_19 | AC | 19 ms
10,496 KB |
testcase_20 | AC | 23 ms
7,040 KB |
testcase_21 | AC | 42 ms
9,216 KB |
testcase_22 | AC | 49 ms
10,880 KB |
testcase_23 | AC | 41 ms
11,008 KB |
testcase_24 | AC | 51 ms
13,972 KB |
testcase_25 | AC | 38 ms
11,008 KB |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; template <typename T> using posteriority_queue = priority_queue<T, vector<T>, greater<T> >; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } template <typename T> void unique(vector<T> &a) { a.erase(unique(ALL(a)), a.end()); } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; struct UnionFind { UnionFind(int n) : data(n, -1) {} int root(int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (data[u] > data[v]) swap(u, v); data[u] += data[v]; data[v] = u; return true; } bool same(int u, int v) { return root(u) == root(v); } int size(int ver) { return -data[root(ver)]; } private: vector<int> data; }; using CostType = ll; struct Edge { int src, dst; CostType cost; Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {} inline bool operator<(const Edge &rhs) const { return cost != rhs.cost ? cost < rhs.cost : dst != rhs.dst ? dst < rhs.dst : src < rhs.src; } inline bool operator<=(const Edge &rhs) const { return !(rhs < *this); } inline bool operator>(const Edge &rhs) const { return rhs < *this; } inline bool operator>=(const Edge &rhs) const { return !(*this < rhs); } }; vector<Edge> detect_bridge(const vector<vector<Edge> > &graph, bool heavy = false) { int n = graph.size(); vector<Edge> res; vector<int> depth(n, -1), imos(n, 0); function<void(int, int)> dfs = [&](int par, int ver) { bool multiedge = false; for (const Edge &e : graph[ver]) { if (depth[e.dst] == -1) { depth[e.dst] = depth[ver] + 1; dfs(ver, e.dst); if (imos[e.dst] == 0) res.emplace_back(min(ver, e.dst), max(ver, e.dst), e.cost); imos[ver] += imos[e.dst]; } else if (!multiedge && e.dst == par) { multiedge = true; } else if (depth[e.dst] < depth[ver]) { ++imos[ver]; --imos[e.dst]; } } }; REP(i, n) { if (depth[i] == -1) { depth[i] = 0; dfs(-1, i); } } if (heavy) { sort(ALL(res), [](const Edge &lhs, const Edge &rhs) { return lhs.src != rhs.src ? lhs.src < rhs.src : lhs.dst != rhs.dst ? lhs.dst < rhs.dst : lhs.cost < rhs.cost; }); } return res; } int main() { int n; cin >> n; UnionFind uf(n); vector<vector<Edge> > graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; graph[u].emplace_back(u, v); graph[v].emplace_back(v, u); uf.unite(u, v); } if (uf.size(0) == n) { cout << "Bob\n"; return 0; } set<int> st; REP(i, n) st.emplace(uf.root(i)); if (st.size() >= 3) { cout << "Alice\n"; return 0; } cout << (detect_bridge(graph).empty() ? "Bob\n" : "Alice\n"); return 0; }