QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378737 | #8575. Three Person Tree Game | ucup-team1055# | WA | 20ms | 3584kb | C++20 | 1.9kb | 2024-04-06 14:25:57 | 2024-04-06 14:25:58 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end();
using ll = long long;
using ld = long double;
using ull = unsigned long long;
bool chmin(auto &a, auto b) {
if(a <= b) return false;
a = b;
return true;
}
bool chmax(auto &a, auto b) {
if(a >= b) return false;
a = b;
return true;
}
void solve() {
int n;
std::cin >> n;
int a,b,c;
std::cin >> a >> b >> c;
a--; b--; c--;
std::vector g(n, std::vector<int>());
rep(i,0,n-1) {
int u,v;
std::cin >> u >> v;
u--; v--;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
std::vector<int> depth(n, 0), par(n, -1);
auto dfs = [&](auto &&self, int v) -> void {
for(auto nv: g[v]) {
if(nv == par[v]) continue;
par[nv] = v;
depth[nv] = depth[v] + 1;
self(self, nv);
}
};
dfs(dfs, a);
auto lca = [&](int u, int v) -> int {
while(depth[u] != depth[v]) {
if(depth[u] < depth[v]) std::swap(u, v);
u = par[u];
}
while(u != v) {
u = par[u];
v = par[v];
}
return u;
};
int m = lca(b, c);
depth.assign(n, 0);
par.assign(n, -1);
dfs(dfs, m);
if(depth[a] < depth[b] && depth[a] <= depth[c] + 1) {
std::cout << "A\n";
}
else if(depth[b] < depth[c] && depth[b] <= depth[a] + 1) {
std::cout << "B\n";
}
else if(depth[c] < depth[a] - 1 && depth[c] <= depth[b]) {
std::cout << "C\n";
}
else {
std::cout << "DRAW\n";
}
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int t;
std::cin >> t;
while(t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: 20ms
memory: 3548kb
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'