結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | null |
提出日時 | 2020-01-31 22:11:15 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,439 bytes |
コンパイル時間 | 1,482 ms |
コンパイル使用メモリ | 155,196 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 16:19:20 |
合計ジャッジ時間 | 2,529 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 4 ms
5,248 KB |
testcase_14 | AC | 4 ms
5,248 KB |
testcase_15 | AC | 4 ms
5,248 KB |
testcase_16 | AC | 4 ms
5,248 KB |
testcase_17 | WA | - |
testcase_18 | AC | 8 ms
5,248 KB |
testcase_19 | AC | 9 ms
5,248 KB |
testcase_20 | AC | 13 ms
5,248 KB |
testcase_21 | AC | 19 ms
5,248 KB |
testcase_22 | AC | 25 ms
5,248 KB |
testcase_23 | AC | 27 ms
5,248 KB |
testcase_24 | WA | - |
testcase_25 | AC | 26 ms
5,248 KB |
ソースコード
/* このコード、と~おれ! Be accepted! ∧_∧ (。・ω・。)つ━☆・*。 ⊂ ノ ・゜+. しーJ °。+ *´¨) .· ´¸.·*´¨) ¸.·*¨) (¸.·´ (¸.·'* ☆ */ #include <stdio.h> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <vector> #include <numeric> #include <iostream> #include <random> #include <map> #include <unordered_map> #include <queue> #include <regex> #include <functional> #include <complex> #include <list> #include <cassert> /*多倍長整数/cpp_intで宣言 #include <boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; */ //#pragma GCC target ("avx2") //#pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") #define rep(i, n) for(int i = 0; i < (n); ++i) #define rep1(i, n) for(int i = 1; i <= (n); ++i) #define rep2(i, n) for(int i = 2; i < (n); ++i) #define repr(i, n) for(int i = n; i >= 0; --i) #define reprm(i, n) for(int i = n - 1; i >= 0; --i) #define printynl(a) printf(a ? "yes\n" : "no\n") #define printyn(a) printf(a ? "Yes\n" : "No\n") #define printYN(a) printf(a ? "YES\n" : "NO\n") #define printin(a) printf(a ? "possible\n" : "imposible\n") #define printdb(a) printf("%.50lf\n", a)//少数出力 #define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ) #define prints(s) printf("%s\n", s.c_str())//string出力 #define all(x) (x).begin(), (x).end() #define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数 #define pb push_back #define priq priority_queue #define rpriq priq<int, vector<int>, greater<int>> #define deg_to_rad(deg) (((deg)/360.0)*2.0*PI) #define rad_to_deg(rad) (((rad)/2.0/PI)*360.0) #define Please return #define AC 0 #define addf(T) [](T a, T b){return (a + b);} #define minf(T) [](T a, T b){return min(a, b);} #define maxf(T) [](T a, T b){return max(a, b);} using ll = long long; constexpr int INF = 1073741823; constexpr int MINF = -1073741823; constexpr ll LINF = ll(4661686018427387903); constexpr ll MOD = 1000000007; const long double PI = acos(-1.0L); using namespace std; void scans(string& str) { char c; str = ""; scanf("%c", &c); if (c == '\n')scanf("%c", &c);//最初の改行対策 while (c != '\n' && c != -1) { str += c; scanf("%c", &c); } } void scanc(char& str) { char c; scanf("%c", &c); if (c == -1)return; while (c == '\n') { scanf("%c", &c); } str = c; } double acot(double x) { return PI / 2 - atan(x); } ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } ll lcm(ll number1, ll number2) {//lcmを求める return number1 / gcd(number1, number2) * number2; } ll LSB(ll n) { return (n & (-n)); } /*-----------------------------------------ここからコード-----------------------------------------*/ //0-indexed struct unionfind { vector<ll> par, siz; unionfind(ll n) : par(n), siz(n) { for (ll i = 0; i < n; ++i) { //全部根で初期化 par[i] = i; //サイズは1 siz[i] = 1; } } void init(ll n) { par.resize(n); siz.resize(n); for (ll i = 0; i < n; ++i) { //全部根で初期化 par[i] = i; //サイズは1 siz[i] = 1; } } //根を返す ll find(ll a) { return par[a] == a ? a : par[a] = find(par[a]); } //くっつける。元から同じだったらfalseを返す bool unite(ll a, ll b) { ll x = find(a), y = find(b); if (x == y)return false; else if (siz[x] < siz[y]) { par[x] = y; siz[y] += siz[x]; } else if (siz[x] > siz[y]) { par[y] = x; siz[x] += siz[y]; } else { par[x] = y; siz[y] += siz[x]; } return true; } //同じ集合か判定する bool same(ll a, ll b) { return find(a) == find(b); } //サイズを返す ll size(ll a) { return siz[find(a)]; } //同じ集合に属す葉を纏めて返す vector<ll> leaf(ll a) { vector<ll> x; ll n = par.size(); for (ll i = 0; i < n; ++i)if (same(a, i))x.pb(i); return x; } }; int main() { int n; scanf("%d", &n); unionfind tree(n); int a, b; rep(i, n - 1) { scanf("%d%d", &a, &b); tree.unite(a, b); } string ans = ""; if (tree.size(0) == n) { ans = "Bob"; } else if(tree.size(0) == (ll)n - 1LL || tree.size(1) == (ll)n - 1LL){ rep(i, n) { if (tree.size(i) == 1)ans = "Bob"; } if (ans == "")ans = "Alice"; } else { ans = "Alice"; } prints(ans); Please AC; }