QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378955#8575. Three Person Tree Gameucup_team_qiuly#WA 2ms8232kbC++142.1kb2024-04-06 15:25:512024-04-06 15:25:53

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 15:25:53]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8232kb
  • [2024-04-06 15:25:51]
  • 提交

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'