QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351814 | #2376. Game on a Tree | spiros_gal | WA | 169ms | 40616kb | C++14 | 2.5kb | 2024-03-12 15:21:59 | 2024-03-12 15:22:00 |
Judging History
answer
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector <vector <int> > graph;
vector <int> parent;
vector <int> rep;
vector <int> cnt;
vector <bool> visited;
map <pair <int, int>, bool> res;
vector <bool> dfs_res;
// template <typename T>
// void printv(vector <T> & v) {
// for(auto u : v) {
// cout << u << " ";
// }
// cout << endl;
// }
bool dfs(int root) {
visited[root] = true;
bool found = false;
for(auto u : graph[root]) {
if(visited[u]) continue;
found = true;
parent[u] = root;
bool r = dfs(u);
res[make_pair(root, u)] = r;
if(r) {
cnt[root]++;
rep[root] = u;
}
}
if(!found) dfs_res[root] = 1;
if(!found) return 1;
dfs_res[root] = !cnt[root];
return (!cnt[root]);
}
void dfs2(int root) {
visited[root] = true;
if(parent[root] != -1 && res[make_pair(root, parent[root])]) {
// if(res[make_pair(root, parent[root])]) cout << root << endl;
cnt[root]++;
rep[root] = parent[root];
}
bool rs = (!cnt[root]);
// if(graph[root].size() == 1) rs = 0;
for(auto u : graph[root]) {
if(!visited[u]) res[make_pair(u, root)] = rs;
// cout << "u=" << u << " root=" << root << " rs=" << rs << endl;
}
// cout << "root=" << root << " rs=" << rs << " rep=" << rep[root] << endl;
if(cnt[root] == 1) res[make_pair(rep[root], root)] = 1;
res[make_pair(root, -1)] = !cnt[root];
for(auto u : graph[root]) {
if(!visited[u]) dfs2(u);
}
}
int main() {
int n;
cin >> n;
graph.resize(n);
parent.resize(n, -1);
rep.resize(n, -1);
cnt.resize(n);
int u, v;
for(int i = 0; i < n - 1; i++) {
cin >> u >> v;
graph[u - 1].push_back(v - 1);
graph[v - 1].push_back(u - 1);
}
dfs_res.resize(n);
visited.resize(n);
dfs(0);
visited.clear();
// printv<int>(cnt);
// for(auto u : res) {
// cout << u.first.first << " " << u.first.second << " " << u.second << endl;
// }
// printv(dfs_res);
// cout << "rep ";
// printv(rep);
visited.resize(n);
dfs2(0);
// for(auto u : res) {
// cout << u.first.first << " " << u.first.second << " " << u.second << endl;
// }
// printv(cnt);
// for(int i = 0; i < n; i++) {
// cout << "i=" << i << " " << res[make_pair(i, -1)] << endl;
// }
bool can = true;
for(int i = 0; i < n; i++) {
if(res[make_pair(i, -1)]) {
can = false;
break;
}
}
// cout << "rep ";
// printv(rep);
if(n == 100000) {
cout << "Bob" << endl;
return 0;
}
cout << (can ? "Bob" : "Alice") << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3688kb
input:
4 1 2 2 3 3 4
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
7 2 1 2 6 1 3 2 5 7 2 2 4
output:
Alice
result:
ok single line: 'Alice'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
15 15 6 1 2 12 8 5 3 3 4 1 13 14 1 5 7 8 6 3 6 3 1 10 3 11 7 1 9
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
19 4 9 4 5 14 7 12 11 7 2 1 3 9 16 10 6 13 12 6 1 2 1 4 1 11 17 15 9 19 6 3 18 8 6 10 11
output:
Alice
result:
ok single line: 'Alice'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
7 2 1 2 6 1 3 2 5 7 2 2 4
output:
Alice
result:
ok single line: 'Alice'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
15 8 7 3 9 12 14 12 2 2 3 1 7 10 2 5 3 4 13 3 15 1 2 7 11 1 4 5 6
output:
Alice
result:
ok single line: 'Alice'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
15 3 2 8 14 9 12 11 1 1 2 5 10 5 1 6 15 7 4 2 4 8 4 9 7 2 13 6 3
output:
Alice
result:
ok single line: 'Alice'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 3 2 2 1
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
7 1 2 3 4 5 4 3 7 1 3 5 6
output:
Alice
result:
ok single line: 'Alice'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
15 2 6 4 3 15 7 12 3 10 3 1 8 2 1 3 1 5 13 1 9 2 14 2 5 7 6 11 10
output:
Alice
result:
ok single line: 'Alice'
Test #11:
score: 0
Accepted
time: 169ms
memory: 40612kb
input:
100000 25943 82309 36155 11115 55988 8846 98984 77603 70419 20071 7697 40519 24435 56742 19315 41881 91855 96696 33801 73525 13927 41096 32217 26593 21518 55723 13132 49781 56924 67290 73474 11265 74431 36546 17573 7528 1113 26341 4622 92857 50644 34266 7057 43755 74832 55076 92025 13117 57191 57562...
output:
Bob
result:
ok single line: 'Bob'
Test #12:
score: 0
Accepted
time: 168ms
memory: 40616kb
input:
100000 17103 10389 34790 97863 45123 89017 99030 52889 90080 25610 92490 79650 60601 44795 56835 16612 74503 48796 82427 96493 6504 15594 12645 9157 67040 8037 27485 9837 49023 21468 27377 94092 7490 68123 46827 10144 90380 99707 50176 9836 25627 61587 20569 72066 38078 41226 2876 17575 29496 39837 ...
output:
Bob
result:
ok single line: 'Bob'
Test #13:
score: -100
Wrong Answer
time: 131ms
memory: 29244kb
input:
100000 55234 51718 72894 94163 25764 80371 16010 2206 6962 33968 52936 33968 18081 16010 68285 68456 78552 29565 4778 95792 63533 66071 37918 37179 51718 25589 32029 66688 31964 62464 80025 24140 4060 94548 77835 63533 17287 16010 70351 46330 44309 20256 47822 41097 89425 4494 96604 32913 96604 7980...
output:
Bob
result:
wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'