QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379871#8575. Three Person Tree Gameucup-team3113#WA 19ms3636kbC++201.5kb2024-04-06 19:38:182024-04-06 19:38:19

Judging History

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

  • [2024-04-06 19:38:19]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:3636kb
  • [2024-04-06 19:38:18]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf = 1e18;

void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}

void solve(){
	int n; cin >> n;
	int sa, sb, sc; cin >> sa >> sb >> sc;
	sa--; sb--; sc--;
	vector<vector<int>>g(n);
	for(int i = 0; i< n-1; i++){
		int c, d; cin >> c >> d;
		c--; d--;
		g[c].pb(d);
		g[d].pb(c);
	}
	
	int rt = -1;
	auto dfs1 = [&](auto&& self, int u, int p)->int{
		int ret = 0;
		for(auto v : g[u])if(v!=p)ret+=self(self, v, u);
		if(u == sb || u == sc)ret++;
		if(rt == -1 && ret == 2)rt = u;
		return ret;
	};
	dfs1(dfs1, sa, sa);
	
	assert(rt != -1);
	
	vector<int>dis(n);
	auto dfs2 = [&](auto&& self, int u, int p)->void{
		for(auto v : g[u])if(v!=p){
			dis[v] = dis[u]+1;
			self(self, v, u);
		}
	};
	dfs2(dfs2, rt, rt);
	
	if(dis[sa] < dis[sb] && dis[sa] <= dis[sc]+1){
		cout << "A\n";
		return;
	}
	if(dis[sb] < dis[sc] && dis[sb] <= dis[sa]){
		cout << "B\n";
		return;
	}
	if(dis[sc]+1 < dis[sa] && dis[sc] <= dis[sb]){
		cout << "C\n";
		return;
	}
	cout << "DRAW\n";
}
	

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	cin >> t;
	while(t--)solve();
}


//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

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: 19ms
memory: 3636kb

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'