Submission #588113
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef vector<int> V; typedef vector<list<int>> ADJ; int bfs(int s,ADJ &adj){ int N=adj.size(); int res=1; queue<int> que; V dist(N,0); dist[s]=dist[0]=1; que.push(s); while(que.empty()==false){ auto v=que.front();que.pop(); for(auto& u : adj[v]) if(dist[u]==0){ dist[u]=1; que.push(u); res++; } } return res; } int main() { int N;cin>>N; ADJ adj(N); for(int i = 0; i < N-1; i++){ int a,b; cin>>a>>b;a--,b--; adj[a].push_back(b); adj[b].push_back(a); } if(adj[0].size()==1){ cout<<"A"<<endl;return 0; } int res=0; for(auto& it : adj[0])res+=(bfs(it,adj)&1); cout<<((res&1)?'A':'B')<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - お祭りとお菓子 |
User | btk15049 |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 914 Byte |
Status | AC |
Exec Time | 205 ms |
Memory | 9240 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt, sample-03.txt |
All | test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, test-21.txt, test-22.txt, test-23.txt, test-24.txt, test-25.txt, test-26.txt, test-27.txt, test-28.txt, test-29.txt, test-30.txt, test-31.txt, test-32.txt, test-33.txt, test-34.txt, test-35.txt, test-36.txt, test-37.txt, test-38.txt, test-39.txt, test-40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample-01.txt | AC | 28 ms | 992 KB |
sample-02.txt | AC | 29 ms | 888 KB |
sample-03.txt | AC | 29 ms | 1020 KB |
test-01.txt | AC | 29 ms | 956 KB |
test-02.txt | AC | 29 ms | 952 KB |
test-03.txt | AC | 29 ms | 956 KB |
test-04.txt | AC | 31 ms | 920 KB |
test-05.txt | AC | 30 ms | 896 KB |
test-06.txt | AC | 30 ms | 956 KB |
test-07.txt | AC | 29 ms | 956 KB |
test-08.txt | AC | 30 ms | 956 KB |
test-09.txt | AC | 30 ms | 952 KB |
test-10.txt | AC | 29 ms | 1020 KB |
test-11.txt | AC | 30 ms | 1020 KB |
test-12.txt | AC | 30 ms | 988 KB |
test-13.txt | AC | 31 ms | 956 KB |
test-14.txt | AC | 32 ms | 1084 KB |
test-15.txt | AC | 36 ms | 1400 KB |
test-16.txt | AC | 42 ms | 1724 KB |
test-17.txt | AC | 58 ms | 2460 KB |
test-18.txt | AC | 107 ms | 5084 KB |
test-19.txt | AC | 101 ms | 4828 KB |
test-20.txt | AC | 133 ms | 6240 KB |
test-21.txt | AC | 151 ms | 7328 KB |
test-22.txt | AC | 148 ms | 7576 KB |
test-23.txt | AC | 183 ms | 9144 KB |
test-24.txt | AC | 182 ms | 8800 KB |
test-25.txt | AC | 187 ms | 9236 KB |
test-26.txt | AC | 192 ms | 8796 KB |
test-27.txt | AC | 184 ms | 9240 KB |
test-28.txt | AC | 205 ms | 9236 KB |
test-29.txt | AC | 188 ms | 9168 KB |
test-30.txt | AC | 181 ms | 8792 KB |
test-31.txt | AC | 185 ms | 9228 KB |
test-32.txt | AC | 178 ms | 8732 KB |
test-33.txt | AC | 173 ms | 8756 KB |
test-34.txt | AC | 172 ms | 8788 KB |
test-35.txt | AC | 179 ms | 8776 KB |
test-36.txt | AC | 193 ms | 9176 KB |
test-37.txt | AC | 195 ms | 9116 KB |
test-38.txt | AC | 179 ms | 8788 KB |
test-39.txt | AC | 194 ms | 8736 KB |
test-40.txt | AC | 188 ms | 9136 KB |