結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | WarToks |
提出日時 | 2020-01-31 22:07:08 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,515 bytes |
コンパイル時間 | 1,493 ms |
コンパイル使用メモリ | 147,112 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2024-11-30 16:19:15 |
合計ジャッジ時間 | 2,725 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | WA | - |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 1 ms
5,248 KB |
testcase_13 | AC | 5 ms
5,248 KB |
testcase_14 | AC | 5 ms
5,248 KB |
testcase_15 | AC | 5 ms
5,248 KB |
testcase_16 | AC | 6 ms
5,248 KB |
testcase_17 | AC | 6 ms
5,248 KB |
testcase_18 | AC | 14 ms
5,248 KB |
testcase_19 | WA | - |
testcase_20 | AC | 22 ms
6,272 KB |
testcase_21 | AC | 34 ms
7,936 KB |
testcase_22 | AC | 44 ms
9,344 KB |
testcase_23 | AC | 49 ms
9,600 KB |
testcase_24 | AC | 54 ms
9,984 KB |
testcase_25 | AC | 49 ms
9,600 KB |
ソースコード
#include <iostream> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cstring> #include <deque> #include <functional> #include <initializer_list> #include <math.h> #include <map> #include <random> #include <set> #include <stack> #include <tuple> #include <type_traits> #include <queue> #include <vector> #define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i)) #define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i)) #define REP(i, n) FOR(i, 0, n) #define rREP(i, n) rFOR(i, 0, (n-1)) #define SORT(A) std::sort((A).begin(), (A).end()) #define ALL(A) (A).begin(), (A).end() // 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A) #define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end()) using lli = long long int; using pii = std::pair<int, int>; // グリッド上の縦横移動 constexpr std::array<std::pair<int, int>, 4> dxdy = { std::pair<int, int>( 1, 0), std::pair<int, int>(-1, 0), std::pair<int, int>( 0, 1), std::pair<int, int>( 0, -1) }; void VintOut(std::vector<int>& A){ const int n = A.size(); if(n == 0){putchar('\n'); return;} printf("%d", A[0]); for(int i = 1; i < n; ++i) printf(" %d", A[i]); putchar('\n'); } void VintOut(std::vector<long long int>& A){ const int n = A.size(); if(n == 0){ putchar('\n'); return;} printf("%lld", A[0]); for(int i = 1; i < n; ++i) printf(" %lld", A[i]); putchar('\n'); } template <typename T> inline bool chmin(T& a, T b){ if(b < a){ 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 bool isIn(int x, int y, int H, int W){ return 0 <= x and x < H and 0 <= y and y < W; } inline bool bitUP(int state, int k){ return (state >> k) & 1; } inline bool bitUP(long long int state, int k){ return (state >> k) & 1;} // z-algorithm template <class T> std::vector<int> z_algorithm(const T &str) { const int n = str.size(); std::vector<int> resOfCP(n); resOfCP[0] = n; int i = 1, j = 0; while (i < n) { while (i + j < n and str[j] == str[i + j]) ++j; resOfCP[i] = j; if (j == 0) { ++i; continue;} int k = 1; while (i + k < n and k + resOfCP[k] < j) resOfCP[i + k] = resOfCP[k], ++k; i += k; j -= k; } return resOfCP; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ constexpr int N = 1e5; std::bitset<N> P; std::vector<std::vector<int>> E; // UnionFind木構造 : 0-indexed | 0, 1, ..., n-1 class UnionFindTree{ private: int n; // 要素数 int numberOfSets; // 集合の数 std::vector<int> Parent; // 親のノード std::vector<int> Size; // 属する集合の大きさ public: // コンストラクタ UnionFindTree(int n):n(n), numberOfSets(n){ Size.assign(n, 1); Parent.resize(n); for(int i = 0; i < n; ++i) Parent[i] = i; } // 集合の大きさを変更する関数 void resize(int sz){ n = sz; numberOfSets = n; Size.assign(n, 1); Parent.resize(n); for(int i = 0; i < n; ++i) Parent[i] = i; } // 頂点 vertex の属する根を返す int rootOf(int vertex){ // 根が自分自身ならば終了 if(Parent[vertex] == vertex) return vertex; // そうでないなら, 親を属する集合の根に付け替える return Parent[vertex] = rootOf(Parent[vertex]); } // 頂点 x, y を併合する : すでに x, yが同じ集合に属しているなら false を返す bool unite(int x, int y){ int root_x = rootOf(x); int root_y = rootOf(y); if(root_x == root_y) return false; if(Size[root_x] < Size[root_y]) std::swap(root_x, root_y); Parent[root_y] = root_x; Size[root_x] += Size[root_y]; numberOfSets--; return true; } // 頂点 x, y が同じ集合に属しているかを判定する関数 inline bool sameSet(int x, int y){ return rootOf(x) == rootOf(y); } // 属している集合の要素数を返す関数 inline int setSize(int vertex){ return Size[rootOf(vertex)]; } // 集合の数を返す inline int getNumberOfSets(void) const { return numberOfSets; } }; int main(void){ int n; scanf("%d", &n); UnionFindTree UFT(n); E.assign(n, std::vector<int>(0)); for(int i = 1; i < n; ++i){ int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); UFT.unite(u, v); } bool flag = false; if(UFT.getNumberOfSets() == 1) flag = true; else if(UFT.getNumberOfSets() == 2){ int root; for(root = 0; root < n; ++root) if(UFT.setSize(root) == n - 1) break; if(root == n) goto OUT; int lsize = 0; std::vector<int> dist(n, -1); dist[root] = 0; std::stack<int> Stk; Stk.push(root); while(not Stk.empty()){ int v = Stk.top(); Stk.pop(); for(int nv : E[v]){ if(dist[nv] == -1){ dist[nv] = dist[v] + 1; Stk.push(nv); } else{ int d = dist[v] + dist[nv] + 1; if(lsize < d) lsize = d; } } } flag = (lsize + 1 == n); } OUT: if(flag) puts("Bob"); else puts("Alice"); return 0; }