結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | stoq |
提出日時 | 2021-08-05 07:17:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 5,047 bytes |
コンパイル時間 | 2,343 ms |
コンパイル使用メモリ | 218,680 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-09-16 15:14:13 |
合計ジャッジ時間 | 4,123 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 5 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,940 KB |
testcase_15 | AC | 6 ms
6,940 KB |
testcase_16 | AC | 5 ms
6,940 KB |
testcase_17 | AC | 5 ms
6,940 KB |
testcase_18 | AC | 13 ms
6,944 KB |
testcase_19 | AC | 13 ms
6,944 KB |
testcase_20 | AC | 21 ms
6,940 KB |
testcase_21 | AC | 39 ms
7,936 KB |
testcase_22 | AC | 47 ms
9,216 KB |
testcase_23 | AC | 49 ms
9,428 KB |
testcase_24 | AC | 45 ms
9,600 KB |
testcase_25 | AC | 49 ms
9,472 KB |
ソースコード
#define MOD_TYPE 1 #pragma region Macros #include <bits/stdc++.h> using namespace std; #if 1 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #if 0 #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/tag_and_trait.hpp> #include <ext/rope> using namespace __gnu_pbds; using namespace __gnu_cxx; template <typename T> using extset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #endif #if 0 #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/cpp_dec_float.hpp> using Int = boost::multiprecision::cpp_int; using lld = boost::multiprecision::cpp_dec_float_100; #endif using ll = long long int; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; using pld = pair<ld, ld>; template <typename T> using smaller_queue = priority_queue<T, vector<T>, greater<T>>; constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353); constexpr int INF = (int)1e9 + 10; constexpr ll LINF = (ll)4e18; constexpr ld PI = acos(-1.0); constexpr ld EPS = 1e-7; constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0}; constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0}; #define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i) #define rep(i, n) REP(i, 0, n) #define REPI(i, m, n) for (int i = m; i < (int)(n); ++i) #define repi(i, n) REPI(i, 0, n) #define MP make_pair #define MT make_tuple #define YES(n) cout << ((n) ? "YES" : "NO") << "\n" #define Yes(n) cout << ((n) ? "Yes" : "No") << "\n" #define possible(n) cout << ((n) ? "possible" : "impossible") << "\n" #define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n" #define all(v) v.begin(), v.end() #define NP(v) next_permutation(all(v)) #define dbg(x) cerr << #x << ":" << x << "\n"; struct io_init { io_init() { cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(30) << setiosflags(ios::fixed); }; } io_init; template <typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } inline ll CEIL(ll a, ll b) { return (a + b - 1) / b; } template <typename A, size_t N, typename T> inline void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } template <typename T, typename U> constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept { is >> p.first >> p.second; return is; } template <typename T, typename U> constexpr ostream &operator<<(ostream &os, pair<T, U> &p) noexcept { os << p.first << " " << p.second; return os; } #pragma endregion random_device seed_gen; mt19937_64 engine(seed_gen()); // -------------------------------------- struct UnionFind { public: UnionFind() : _n(0) {} UnionFind(int n) : _n(n), parent_or_size(n, -1) {} int unite(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = root(a), y = root(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return root(a) == root(b); } int root(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = root(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[root(a)]; } vector<vector<int>> groups() { vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = root(i); group_size[leader_buf[i]]++; } vector<vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector<int> &v) { return v.empty(); }), result.end()); return result; } private: int _n; vector<int> parent_or_size; }; void solve() { int n; cin >> n; vector<vector<int>> E(n); vector<int> deg(n, 0); UnionFind uf(n); rep(i, n - 1) { int u, v; cin >> u >> v; uf.unite(u, v); E[u].push_back(v); E[v].push_back(u); deg[u]++, deg[v]++; } set<int> roots; rep(i, n) roots.insert(uf.root(i)); if (roots.size() >= 3) { cout << "Alice\n"; return; } else if (roots.size() == 1) { cout << "Bob\n"; return; } auto itr = roots.begin(); int a = *itr; itr++; int b = *itr; if (uf.size(a) >= 2 and uf.size(b) >= 2) { cout << "Alice\n"; return; } // ループかチェック rep(i, n) { if (deg[i] == 1) { cout << "Alice\n"; return; } } cout << "Bob\n"; } int main() { solve(); }