QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379296#8575. Three Person Tree Gameucup-team266#WA 42ms17932kbC++232.3kb2024-04-06 16:58:392024-04-06 16:58:39

Judging History

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

  • [2024-04-06 16:58:39]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:17932kb
  • [2024-04-06 16:58:39]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[200200];
int anc[19][200200];
int depth[200200];
void dfs(int u,int fa)
{
	depth[u]=depth[fa]+1;
	anc[0][u]=fa;
	for(auto v:G[u])
		if(v!=fa)
			dfs(v,u);
}
int lca(int u,int v)
{
	for(int i=18;i>=0;i--)
	{
		if(depth[anc[i][u]]>=depth[v])
			u=anc[i][u];
		if(depth[anc[i][v]]>=depth[u])
			v=anc[i][v];
	}
	if(u==v) return u;
	for(int i=18;i>=0;i--)
		if(anc[i][u]!=anc[i][v])
		{
			u=anc[i][u];
			v=anc[i][v];
		}
	return anc[0][u];
}
int dist(int u,int v)
{
	return depth[u]+depth[v]-2*depth[lca(u,v)];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
			G[i].clear();
		int a,b,c;
		cin>>a>>b>>c;
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].pb(v);
			G[v].pb(u);
		}
		dfs(1,0);
		for(int i=1;i<19;i++)
			for(int j=1;j<=n;j++)
				anc[i][j]=anc[i-1][anc[i-1][j]];
		int rt=1;
		int sm=inf;
		for(int i=1;i<=n;i++)
		{
			int sum=dist(i,a)+dist(i,b)+dist(i,c);
			if(sum<sm)
			{
				sm=sum;
				rt=i;
			}
		}
		int dA=dist(a,rt),dB=dist(b,rt),dC=dist(c,rt);
		int mn=min({dA,dB,dC});
		if(max({dA,dB,dC})==mn)
			puts("DRAW");
		else if(dA==mn&&dB==mn)
			puts("B");
		else if(dA==mn&&dC==mn)
			puts("A");
		else if(dB==mn&&dC==mn)
		{
			if(dA==mn+1)
				puts("DRAW");
			else
				puts("C");
		}
		else if(dA==mn)
			puts("A");
		else if(dB==mn)
			puts("B");
		else
		{
			assert(dC==mn);
			if(dA==mn+1)
			{
				if(dB==mn+1)
					puts("DRAW");
				else
					puts("A");
			}
			else
				puts("C");
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 17908kb

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: 42ms
memory: 17932kb

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'