QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #352005 | #2376. Game on a Tree | spiros_gal | WA | 249ms | 28368kb | C++14 | 3.5kb | 2024-03-12 19:15:23 | 2024-04-09 18:26:03 |
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;
// }
// }
// return (!cnt[root]);
// }
void dfs(int root) {
stack <int> st;
st.push(root);
while(!st.empty()) {
root = st.top();
visited[root] = true;
bool found = false;
for(auto u : graph[root]) {
if(visited[u]) continue;
found = true;
parent[u] = root;
st.push(u);
}
if(!found) {
st.pop();
for(auto u : graph[root]) {
if(u != parent[root]) {
bool r = dfs_res[u];
res[make_pair(root, u)] = r;
if(r) {
cnt[root]++;
rep[root] = u;
}
}
}
dfs_res[root] = !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);
// }
// }
void dfs2(int root) {
stack<int> st;
st.push(root);
while(!st.empty()) {
int root = st.top();
st.pop();
visited[root] = true;
if(parent[root] != -1 && res[make_pair(root, parent[root])]) {
cnt[root]++;
rep[root] = parent[root];
}
bool rs = !cnt[root];
for(auto u : graph[root]) {
if(!visited[u]) res[make_pair(u, root)] = rs;
}
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]) st.push(u);
}
}
}
int main() {
int n;
cin >> n;
graph.resize(n);
parent.resize(n, -1);
rep.resize(n, -1);
cnt.resize(n);
dfs_res.resize(n, 1);
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);
}
visited.resize(n);
dfs(0);
visited.clear();
// printv<int>(cnt);
// for(auto u : res) {
// cout << u.first.first << " " << u.first.second << " " << u.second << endl;
// }
// 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);
cout << (can ? "Bob" : "Alice") << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
4 1 2 2 3 3 4
output:
Bob
result:
ok single line: 'Bob'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
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: 3600kb
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: 3620kb
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: 3528kb
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: 3532kb
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: 3620kb
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: 3532kb
input:
3 3 2 2 1
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3528kb
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: 3608kb
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: -100
Wrong Answer
time: 249ms
memory: 28368kb
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:
Alice
result:
wrong answer 1st lines differ - expected: 'Bob', found: 'Alice'