QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #439209 | #8575. Three Person Tree Game | real_sigma_team# | WA | 29ms | 3608kb | C++20 | 2.2kb | 2024-06-11 18:08:20 | 2024-06-11 18:08:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
int a, b, c;
cin >> a >> b >> c;
--a, --b, --c;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> da(n), db(n), dc(n);
auto calc_dist = [&](auto calc_dist, int u, int p, vector<int>& d) -> void {
for (auto to : g[u]) {
if (to != p) {
d[to] = d[u] + 1;
calc_dist(calc_dist, to, u, d);
}
}
};
calc_dist(calc_dist, a, -1, da);
calc_dist(calc_dist, b, -1, db);
calc_dist(calc_dist, c, -1, dc);
string res = "DRAW";
for (int iter = 0; iter < 3; ++iter) {
vector<int> can(n);
vector<int> par(n, -1);
can[c] = true;
auto dfs = [&](auto dfs, int u, int p) -> void {
par[u] = p;
for (auto to : g[u]) {
if (to != p) {
if (can[u]) can[to] = 1;
dfs(dfs, to, u);
can[u] += can[to];
}
}
};
dfs(dfs, a, -1);
vector<bool> used(n, false);
int b_ = b;
used[b] = can[b];
while (par[b] != -1) {
if (can[par[b]] > can[b]) used[par[b]] = true;
b = par[b];
}
b = b_;
bool ok = false;
for (int i = 0; i < n; ++i) {
if (!used[i]) continue;
ok |= da[i] >= db[i] - (iter == 2);
}
if (!ok) {
res = char('A' + iter);
}
swap(da, dc);
swap(da, db);
swap(a, c);
swap(a, b);
}
cout << res << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
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: 29ms
memory: 3484kb
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 DRAW B DRAW DRAW DRAW DRAW DRAW DRAW C DRAW B DRAW DRAW A DRAW A DRAW DRAW DRAW DRAW DRAW A A B B B DRAW A A DRAW B B DRAW C DRAW A A DRAW DRAW DRAW DRAW B DRAW C DRAW A B DRAW B DRAW DRAW DRAW DRAW DRAW DRAW C DRAW DRAW A DRAW DRAW DRAW DRAW B DRAW B DRAW DRAW B DRAW DRAW A DRAW DRAW DRAW DRAW ...
result:
wrong answer 3rd lines differ - expected: 'C', found: 'DRAW'