QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378957 | #8575. Three Person Tree Game | ucup_team_qiuly# | WA | 9ms | 8324kb | C++14 | 2.1kb | 2024-04-06 15:26:34 | 2024-04-06 15:26:35 |
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: 100
Accepted
time: 3ms
memory: 8324kb
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: 9ms
memory: 8296kb
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'