QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379022#8575. Three Person Tree Gameucup-team052#AC ✓58ms22076kbC++231.2kb2024-04-06 15:51:032024-04-06 15:51:04

Judging History

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

  • [2024-04-06 15:51:04]
  • 评测
  • 测评结果:AC
  • 用时:58ms
  • 内存:22076kb
  • [2024-04-06 15:51:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,a,b,c;
vector<int> G[N];
int dep[N],fa[N];
void dfs1(int u,int fa)
{
	dep[u]=dep[fa]+1;
	::fa[u]=fa;
	for(int v:G[u])
	{
		if(v==fa) continue;
		dfs1(v,u);
	}
}
int lca(int u,int v)
{
	while(dep[u]!=dep[v])
	{
		if(dep[u]>dep[v]) u=fa[u];
		else v=fa[v];
	}
	while(u!=v) u=fa[u],v=fa[v];
	return u;
}
void work()
{
	scanf("%d%d%d%d",&n,&a,&b,&c);
	for(int i=1;i<=n;i++) G[i].clear(),fa[i]=0,dep[i]=0;
	for(int i=1;i<n;i++)
	{
		int u,v; scanf("%d %d",&u,&v);
		G[u].push_back(v),G[v].push_back(u);
	}
	dfs1(a,0);
	if(dep[c]-dep[a]==1) printf("A\n");
//	else if((L==b||L==c)&&abs(dep[b]-dep[c])==1) printf("B\n");
	else
	{
		int L=lca(b,c);
		int da=dep[L]-dep[a],db=dep[b]-dep[L],dc=dep[c]-dep[L];
		int wina=(da<db)&&(da<dc+2);
		int winb=(db<dc)&&(db<=da);
		int winc=(dc<=da-2)&&(dc<=db);
		assert(wina+winb+winc<=1);
		if(wina) printf("A\n");
		else if(winb) printf("B\n");
		else if(winc) printf("C\n");
		else printf("DRAW\n");
	}
}
signed main()
{
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	int T; cin>>T; while(T--) work();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 15ms
memory: 3752kb

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
A
B
A
A
A
B
B
B
C
A
A
A
B
B
DRAW
C
DRAW
A
A
A
A
A
B
B
A
C
DRAW
A
B
A
B
DRAW
A
C
DRAW
A
B
C
DRAW
DRAW
A
A
A
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
A
B
B
B
A
A
B
B
A
C
DRAW
B
A
B
A
A
A
C
A
A
DRAW
A
A
C
A
DRAW
C
A
B
A...

result:

ok 10000 lines

Test #3:

score: 0
Accepted
time: 23ms
memory: 4008kb

input:

100
2000
455 1301 981
1508 1509
1242 1243
1261 1260
190 191
1981 1980
591 592
1792 1791
1726 1727
959 960
134 135
1193 1192
836 835
1803 1804
1577 1578
1548 1549
718 717
1294 1295
1116 1117
59 58
138 139
425 426
1168 1169
1963 1962
1025 1026
867 866
892 893
589 588
871 872
891 892
722 721
1711 1712
...

output:

C
A
A
B
DRAW
C
A
B
B
DRAW
B
C
B
A
DRAW
B
C
A
C
DRAW
C
B
A
C
DRAW
A
C
C
C
DRAW
B
A
A
C
DRAW
C
A
B
C
DRAW
B
A
B
A
DRAW
A
C
B
A
DRAW
B
C
C
C
DRAW
A
B
B
C
DRAW
C
B
C
A
DRAW
A
C
B
A
DRAW
B
A
B
A
DRAW
C
A
C
B
DRAW
A
B
C
C
DRAW
C
B
C
A
DRAW
B
A
C
B
DRAW
A
A
A
C
DRAW

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 58ms
memory: 22076kb

input:

1
200000
123236 117321 150583
47722 47723
103604 103605
48192 48191
19204 19205
3666 3667
190708 190709
111542 111541
16125 16124
164298 164299
55406 55405
62042 62041
42100 42101
40664 40663
131742 131743
105518 105517
24249 24250
174387 174388
29840 29841
164536 164537
54802 54803
6378 6377
97486 ...

output:

A

result:

ok single line: 'A'

Test #5:

score: 0
Accepted
time: 49ms
memory: 16240kb

input:

1
200000
151854 28266 141391
178840 177656
70949 127572
92675 174074
38426 55569
16718 64264
72596 171817
36908 36081
44793 65081
114199 93358
10460 36725
18563 26764
77047 29901
17769 39712
109495 141203
24130 37855
165153 135141
94225 107789
57603 49313
197306 48518
61030 57058
199291 42676
60161 ...

output:

B

result:

ok single line: 'B'

Test #6:

score: 0
Accepted
time: 50ms
memory: 20632kb

input:

1
200000
107496 54564 62204
75611 75612
33562 133562
66786 66785
35079 35078
40044 40045
99675 199675
121963 21963
15671 15672
3062 103062
71627 171627
27125 127125
30049 30048
63164 63165
183373 83373
51319 51320
99879 199879
36383 136383
89110 89109
7607 107607
20098 20099
57792 157792
100415 415
...

output:

B

result:

ok single line: 'B'

Test #7:

score: 0
Accepted
time: 55ms
memory: 16332kb

input:

1
200000
158505 85726 178357
30247 29809
107160 107392
84411 84297
80963 81018
64893 65118
194706 194894
8253 8478
47677 48197
120341 120487
68388 68653
41048 40580
128093 127913
118156 117983
97582 97422
166508 166267
171977 171895
108683 108912
102410 102283
130584 130479
75441 75592
145257 145092...

output:

A

result:

ok single line: 'A'

Test #8:

score: 0
Accepted
time: 8ms
memory: 3840kb

input:

10992
3
1 2 3
2 1
3 1
3
1 3 2
2 1
3 1
3
2 1 3
2 1
3 1
3
2 3 1
2 1
3 1
3
3 1 2
2 1
3 1
3
3 2 1
2 1
3 1
4
1 2 3
2 1
3 2
4 1
4
1 2 4
2 1
3 2
4 1
4
1 3 2
2 1
3 2
4 1
4
1 3 4
2 1
3 2
4 1
4
1 4 2
2 1
3 2
4 1
4
1 4 3
2 1
3 2
4 1
4
2 1 3
2 1
3 2
4 1
4
2 1 4
2 1
3 2
4 1
4
2 3 1
2 1
3 2
4 1
4
2 3 4
2 1
3 2
4 ...

output:

A
A
B
A
B
A
B
A
A
A
A
A
A
B
A
A
A
A
A
B
B
B
C
A
B
B
A
B
A
C
A
A
A
A
A
A
B
B
A
DRAW
A
DRAW
B
B
A
DRAW
A
DRAW
B
B
A
DRAW
A
DRAW
B
A
A
A
A
A
A
A
B
A
A
A
A
B
B
A
A
A
A
A
B
A
A
C
A
B
B
B
B
B
C
A
B
C
A
C
B
B
A
A
B
A
A
C
A
A
A
A
B
B
A
C
B
A
C
C
A
B
B
B
B
A
A
A
A
A
A
A
A
A
A
A
A
B
B
A
A
A
A
A
DRAW
A
A
DRAW
...

result:

ok 10992 lines

Test #9:

score: 0
Accepted
time: 14ms
memory: 3844kb

input:

22222
9
1 2 3
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 4
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 5
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 6
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 7
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 8
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 9
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 3 2
2 1
3 ...

output:

B
B
B
A
A
A
A
A
B
B
A
A
A
A
A
C
B
A
A
A
A
A
C
C
A
A
A
A
A
A
A
A
B
B
B
A
A
A
A
A
B
B
A
A
A
A
A
C
B
A
A
A
A
A
C
C
A
A
A
B
B
B
B
A
B
B
A
A
A
A
A
A
B
A
A
A
A
A
A
C
A
A
A
A
A
A
A
A
B
B
B
A
A
A
A
C
B
B
A
A
A
A
C
C
B
A
A
A
A
C
C
C
A
A
A
B
B
B
B
B
A
A
B
B
B
B
A
A
B
A
A
A
A
A
A
A
A
A
A
A
C
A
A
A
B
B
B
C
A
A
...

result:

ok 22222 lines

Extra Test:

score: 0
Extra Test Passed