結果
問題 | No.977 アリス仕掛けの摩天楼 |
ユーザー | otamay6 |
提出日時 | 2020-01-31 21:45:43 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 2,528 bytes |
コンパイル時間 | 1,913 ms |
コンパイル使用メモリ | 178,912 KB |
実行使用メモリ | 10,440 KB |
最終ジャッジ日時 | 2023-10-17 09:07:37 |
合計ジャッジ時間 | 3,667 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 3 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,348 KB |
testcase_13 | AC | 10 ms
4,348 KB |
testcase_14 | AC | 9 ms
4,348 KB |
testcase_15 | AC | 9 ms
4,348 KB |
testcase_16 | AC | 9 ms
4,348 KB |
testcase_17 | AC | 9 ms
4,348 KB |
testcase_18 | AC | 27 ms
5,424 KB |
testcase_19 | AC | 28 ms
5,424 KB |
testcase_20 | AC | 44 ms
6,744 KB |
testcase_21 | AC | 72 ms
8,592 KB |
testcase_22 | AC | 96 ms
10,176 KB |
testcase_23 | AC | 101 ms
10,440 KB |
testcase_24 | AC | 93 ms
10,440 KB |
testcase_25 | AC | 104 ms
10,440 KB |
ソースコード
#include<bits/stdc++.h> #define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i) #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define All(x) (x).begin(),(x).end() #define rAll(x) (x).rbegin(),(x).rend() using namespace std; using ll = long long; class UnionFind{ private: vector<int> Parent,es; vector<ll> diff_weight; public: UnionFind(int N){ es.resize(N,0); Parent.resize(N,-1); diff_weight.resize(N,0LL); } int root(int A){ if(Parent[A]<0) return A; else{ int r = root(Parent[A]); diff_weight[A] += diff_weight[Parent[A]]; // 累積和をとる return Parent[A]=r; } } bool issame(int A,int B){ return root(A)==root(B); } ll weight(int x) { root(x); // 経路圧縮 return diff_weight[x]; } ll diff(int x, int y) { return weight(y) - weight(x); } int size(int A){ return -Parent[root(A)]; } int eize(int A){ return es[root(A)]; } bool connect(int A,int B){ A=root(A); B=root(B); if(A==B) return false; if(size(A)<size(B)) std::swap(A,B); Parent[A]+=Parent[B]; es[A]+=es[B]+1; Parent[B]=A; return true; } void unite(int A,int B){ A=root(A); B=root(B); if(A==B){ es[A]++; return; } if(size(A)<size(B)) std::swap(A,B); Parent[A]+=Parent[B]; es[A]+=es[B]+1; Parent[B]=A; return; } bool merge(int A, int B, ll w) { // x と y それぞれについて、 root との重み差分を補正 w += weight(A); w -= weight(B); A=root(A); B=root(B); if(A==B) return false; if(size(A)<size(B)) std::swap(A,B),w=-w; Parent[A]+=Parent[B]; Parent[B]=A; // x が y の親になるので、x と y の差分を diff_weight[y] に記録 diff_weight[B] = w; return true; } }; int main(){ int N;cin>>N; UnionFind uni(N); vector<vector<int>> graph(N); REP(i,N-1){ int a,b;cin>>a>>b; uni.connect(a,b); graph[a].push_back(b); graph[b].push_back(a); } int ans=0,u=0; REP(i,N) if(!uni.issame(0,i)) ans++,u=i; if(ans==0) cout<<"Bob"<<endl; else if(ans==1){ REP(i,N) if(graph[i].size()&1){ cout<<"Alice"<<endl; return 0; } cout<<"Bob"<<endl; } else cout<<"Alice"<<endl; }