QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378955 | #8575. Three Person Tree Game | ucup_team_qiuly# | WA | 2ms | 8232kb | C++14 | 2.1kb | 2024-04-06 15:25:51 | 2024-04-06 15:25:53 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
x = 0, _f = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = - x;
}
// const int mod = 998244353;
// inline int mul (int x, int y) { return 1ll * x * y % mod; }
// inline int qpow (int x, int y, int r = 1) { for ( ; y; y >>= 1, x = mul (x, x)) if (y & 1) r = mul (r, x); return r; }
// inline void pls (int & x, int y) { x += y; if (x >= mod) x -= mod; }
// inline int add (int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
inline void answer (int a, int b, int c) {
// debug ("%d, %d, %d\n", a, b, c);
auto equal = [&] (int x, int y, int z) { return x == y && y == z; };
if (equal (a, b, c) || equal (a - 1, b, c) || equal (a - 1, b - 1, c)) return puts ("Draw"), void ();
if (a < b && a - 1 <= c) return puts ("A"), void ();
if (b <= a && b < c) return puts ("B"), void ();
if (c <= b && c < a - 1) return puts ("C"), void ();
}
const int N = 2e5 + 5;
int n, a, b, c;
vector <int> to[N];
int rt;
int findrt (int u, int pre) {
int s = u == a || u == b || u == c;
for (auto & v : to[u]) if (v != pre) s += findrt (v, u);
if (! rt && s > 1) rt = u;
return s;
}
int A, B, C;
void dfs (int u, int pre, int dist = 0) {
if (u == a) A = dist;
if (u == b) B = dist;
if (u == c) C = dist;
for (auto & v : to[u]) if (v != pre) dfs (v, u, dist + 1);
}
inline void testcase () {
IN (n), IN (a), IN (b), IN (c);
lep (i, 1, n) to[i].clear ();
for (int u, v, i = 1; i < n; ++ i) {
IN (u), IN (v);
to[u].emplace_back ( v );
to[v].emplace_back ( u );
}
rt = 0, findrt (1, 0);
dfs (rt, 0), answer (A, B, C);
}
signed main () {
int t; IN (t);
while (t -- ) testcase ();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 8232kb
input:
2 3 1 2 3 2 1 3 1 4 1 2 3 1 4 2 4 3 4
output:
A Draw
result:
wrong answer 2nd lines differ - expected: 'DRAW', found: 'Draw'