QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #378371 | #8575. Three Person Tree Game | ucup-team2894# | WA | 15ms | 8280kb | C++17 | 3.5kb | 2024-04-06 12:15:39 | 2024-04-06 12:15:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> graph[200005];
int nd[3];
int under[3];
int par[200005];
int dep[200005];
bool onpath[200005];
void dfs(int n) {
for (int e : graph[n]) {
if (e != par[n]) {
par[e] = n;
dep[e] = dep[n] + 1;
dfs(e);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--) {
cin >> N;
cin >> nd[0] >> nd[1] >> nd[2];
for (int i = 1; i <= N; i++) {
graph[i].clear();
par[i] = 0;
onpath[i] = 0;
dep[i] = 0;
}
for (int i = 1; i < N; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
bool done = 0;
for (int e : graph[nd[0]]) {
if (e == nd[2]) {
cout << 'A' << "\n";
done = 1;
break;
}
}
if (done) {
continue;
}
dfs(nd[0]);
int cur = nd[1];
onpath[nd[0]] = 1;
while(cur != nd[0]) {
onpath[cur] = 1;
cur = par[cur];
}
int root = nd[2];
while(!onpath[root]) {
root = par[root];
}
fill(par, par+1+N, 0);
fill(dep, dep+1+N, 0);
dfs(root);
// cout << root << endl;
if (dep[nd[0]] == dep[nd[2]] && dep[nd[1]] == dep[nd[2]]) {
cout << "DRAW\n";
continue;
}
if (dep[nd[0]] - 1 == dep[nd[2]] && dep[nd[1]] == dep[nd[2]]) {
cout << "DRAW\n";
continue;
}
if (dep[nd[0]] - 1 == dep[nd[2]] && dep[nd[1]] - 1 == dep[nd[2]]) {
cout << "DRAW\n";
continue;
}
int mndep = min({dep[nd[0]], dep[nd[1]], dep[nd[2]]});
int ans = 0;
if (dep[nd[0]] == mndep && dep[nd[1]] == mndep) {
ans = 1;
}
else if (dep[nd[1]] == mndep && dep[nd[2]] == mndep) {
ans = 2;
}
else if (dep[nd[0]] == mndep && dep[nd[2]] == mndep) {
ans = 0;
}
else {
for (int i = 0; i < 3; i++) {
if (dep[nd[i]] == mndep) {
ans = i;
break;
}
}
}
cout << "ABC"[ans] << "\n";
// for (int k = 0; k < 3; k++) {
// under[k] = nd[k];
// while(par[under[k]] != root && under[k] != root) {
// under[k] = par[under[k]];
// }
// }
// int t = 0;
// while (nd[0] != root && nd[1] != root && nd[2] != root) {
// if (nd[0] == under[0] && nd[1] == under[1] && nd[2] == under[2]) {
// cout << "DRAW\n";
// done = 1;
// break;
// }
// nd[t] = par[nd[t]];
// t = (t + 1) % 3;
// }
// if (done) {
// continue;
// }
// int atRoot = 0;
// if (nd[1] == root) {
// atRoot = 1;
// }
// if (nd[2] == root) {
// atRoot = 2;
// }
// int ans = atRoot;
// if (nd[(atRoot+1)%3] == under[(atRoot+1)%3]) {
// ans = (atRoot+1)%3;
// }
// cout << "ABC"[ans] << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8268kb
input:
2 3 1 2 3 2 1 3 1 4 1 2 3 1 4 2 4 3 4
output:
A DRAW
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 15ms
memory: 8280kb
input:
10000 20 2 12 1 16 15 3 2 16 17 14 13 11 12 9 8 10 9 18 17 6 5 18 19 13 12 5 4 7 6 20 19 14 15 3 4 11 10 1 2 8 7 20 12 13 1 18 13 12 11 19 15 17 16 10 14 4 2 15 11 6 5 3 2 4 13 20 8 11 9 3 7 14 16 5 8 5 4 9 6 10 3 1 2 17 2 17 15 9 10 5 4 9 8 2 11 6 7 8 7 13 4 2 3 6 15 5 6 17 8 2 1 3 4 16 7 14 5 3 12...
output:
A B C B DRAW C A A A DRAW C B B B DRAW A DRAW A C DRAW A B A A A B B B C A A A B B DRAW C DRAW A A A A A B B A C DRAW A B A B DRAW A C DRAW A B C DRAW DRAW A A A DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B C C DRAW A B A A A B B B A A B B A C DRAW B A B A A A C A A DRAW A A C A DRAW C A B A...
result:
wrong answer 83rd lines differ - expected: 'A', found: 'C'