QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379963#8575. Three Person Tree Gameucup-team027#WA 23ms3832kbC++232.3kb2024-04-06 20:15:342024-04-06 20:15:49

Judging History

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

  • [2024-04-06 20:15:49]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:3832kb
  • [2024-04-06 20:15:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

struct LCA {
	int T = 0;
	vi time, path, ret, depth;
	RMQ<int> rmq;

	LCA(vector<vi>& C) : time(sz(C)), depth(sz(C)), rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++; if (par != -1) depth[v] = depth[par]+1;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}
	int dist(int a, int b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
};

void solve() {
	int n; cin >> n;
	int a, b, c;
	cin >> a >> b >> c; a--, b--, c--;
	vector<vector<int>> g(n);
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y; x--, y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	LCA lca(g);

	int mndist = 998244353, piv = 0;
	for (int i = 0; i < n; i++) {
		int dist = 0;
		dist += lca.dist(a, i);
		dist += lca.dist(b, i);
		dist += lca.dist(c, i);

		if (dist < mndist) {
			mndist = dist;
			piv = i;
		}
	}

	int da = lca.dist(a, piv);
	int db = lca.dist(b, piv);
	int dc = lca.dist(c, piv);
	
	// a win?
	if (da <= dc+1 && db > da) {
		cout << "A\n"; return;
	}

	// b win?
	if (db <= da && dc > db) {
		cout << "B\n"; return;
	}

	// c win?
	if (dc <= db && da > dc+1) {
		cout << "C\n"; return;
	}

	// draw
	cout << "DRAW\n";
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3832kb

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: 23ms
memory: 3584kb

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'