QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380531 | #8575. Three Person Tree Game | ucup-team1766# | WA | 13ms | 3620kb | C++17 | 1.3kb | 2024-04-07 05:32:22 | 2024-04-07 05:32:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<int> tree[], vector<int> &par, int cur, int prev) {
par[cur] = prev;
for (int nei : tree[cur]) {
if (nei != prev) {
dfs(tree, par, nei, cur);
}
}
}
void solve() {
int N;
cin >> N;
int a, b, c;
cin >> a >> b >> c;
a--; b--; c--;
vector<int> tree[N];
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
vector<int> par(N);
dfs(tree, par, a, -1);
vector<int> marks(N, -1);
int cur = b;
int cnt = 0;
while (cur != -1) {
marks[cur] = cnt;
cur = par[cur];
cnt++;
}
cur = c;
cnt = 0;
int adist, bdist, cdist, center;
while (cur != -1) {
if (marks[cur] >= 0) {
bdist = marks[cur];
cdist = cnt;
center = cur;
break;
}
cur = par[cur];
cnt++;
}
cur = center;
adist = 0;
while (cur != a) {
adist++;
cur = par[cur];
}
if (adist < bdist && adist - 1 <= cdist) {
cout << "A\n";
} else if (bdist <= adist && bdist < cdist) {
cout << "B\n";
} else if (cdist <= bdist && cdist < adist - 1) {
cout << "C\n";
} else {
cout << "DRAW\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T; while (T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
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: 13ms
memory: 3564kb
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 DRAW B A A A B B B C A A A B B DRAW C DRAW A A DRAW A A B B DRAW C DRAW A B DRAW B DRAW A C DRAW DRAW B C DRAW DRAW A A DRAW DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B A C DRAW A B A A DRAW B B B A A B B A C DRAW B A B DRAW A A C A A D...
result:
wrong answer 21st lines differ - expected: 'A', found: 'DRAW'