QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352003 | #2376. Game on a Tree | spiros_gal | WA | 0ms | 3616kb | C++14 | 3.5kb | 2024-03-12 19:14:58 | 2024-03-12 19:14:58 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3616kb
input:
4 1 2 2 3 3 4
output:
i=0 0 i=1 0 i=2 0 i=3 0 Bob
result:
wrong answer 1st lines differ - expected: 'Bob', found: 'i=0 0'