QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #379616 | #8575. Three Person Tree Game | ucup-team191# | WA | 16ms | 5860kb | C++23 | 1.9kb | 2024-04-06 17:58:33 | 2024-04-06 17:58:58 |
Judging History
answer
#include <cstdio>
#include <vector>
#define PB push_back
using namespace std;
const int N = 2e5 + 500;
const int LOG = 20;
int par[N][LOG], dep[N], n, A, B, C;
vector < int > v[N];
void dfs(int x, int lst) {
par[x][0] = lst; dep[x] = dep[lst] + 1;
for(int y : v[x]) {
if(y != lst) dfs(y, x);
}
}
void precompute() {
for(int j = 1;j < LOG;j++)
for(int i = 1;i <= n;i++)
par[i][j] = par[par[i][j - 1]][j - 1];
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int j = LOG - 1;j >= 0 ; j--)
if(dep[x] - (1 << j) >= dep[y])
x = par[x][j];
if(x == y) return x;
for(int j = LOG - 1;j >= 0;j--)
if(par[x][j] != par[y][j])
x = par[x][j], y = par[y][j];
return par[x][0];
}
int dist(int x, int y) {
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
void solve() {
scanf("%d%d%d%d", &n, &A, &B, &C);
for(int i = 1;i <= n;i++) v[i].clear();
for(int i = 1;i < n;i++) {
int x, y; scanf("%d%d", &x, &y);
v[x].PB(y), v[y].PB(x);
}
dep[1] = -1; dfs(1, 1);
precompute();
int AB = dist(A, B);
int AC = dist(A, C);
int BC = dist(B, C);
if(AC == 1) {
printf("A\n");
return;
}
if(AB + AC == BC) {
printf("A\n");
return;
} else if(AB + BC == AC) {
printf("B\n");
return;
} else if(AC + BC == AB) {
printf("C\n");
return;
}
int lAB = lca(A, B), lAC = lca(A, C), lBC = lca(B, C);
int D = lAB;
if(dep[lAC] > dep[D]) D = lAC;
if(dep[lBC] > dep[D]) D = lBC;
int AD = dist(A, D), BD = dist(B, D), CD = dist(C, D);
if(AD < BD && AD < CD) {
printf("A\n");
} else if(BD < AD && BD < CD) {
printf("B\n");
} else if(CD < BD && CD < AD - 1) {
printf("C\n");
} else if(AD == BD && AD < CD) {
printf("B\n");
} else if(AD == CD && AD < BD) {
printf("A\n");
} else if(BD == CD && BD < AD - 1) {
printf("C\n");
} else {
printf("DRAW\n");
}
}
int main() {
int T; scanf("%d", &T);
for(;T--;) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5860kb
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: 16ms
memory: 5784kb
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 DRAW 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 ...
result:
wrong answer 83rd lines differ - expected: 'A', found: 'DRAW'