QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379169#8575. Three Person Tree Gameucup-team3396#WA 11ms18912kbC++141.9kb2024-04-06 16:28:062024-04-06 16:28:07

Judging History

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

  • [2024-04-06 16:28:07]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:18912kb
  • [2024-04-06 16:28:06]
  • 提交

answer

#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=5e5+9;
ll T,n,A,B,C,fa[N],dep[N],tag[N];
vector<ll>to[N];
void dfs(ll x,ll f){
	fa[x]=f,dep[x]=dep[f]+1;
	for(ll y:to[x]){
		if(y==f)continue;
		dfs(y,x);
	}
}
ll LCA(ll x,ll y){
	rep(i,0,n)tag[i]=0;
	while(x)tag[x]=1,x=fa[x];
	while(y){
		if(tag[y])return y;
		y=fa[y];
	}
	return 0;
}
void solve(){
	n=read();
	A=read(),B=read(),C=read();
	rep(i,1,n)to[i].clear();
	rep(i,2,n){
		ll x=read(),y=read();
		to[x].push_back(y);
		to[y].push_back(x);
	}
	//链的情况
	//如果 A 是中点,A 必胜
	//如果 B 是中点,B 必胜
	//如果 C 是中点,需要判断 A 是否一步杀 C
	//三岔的情况
	//找出三个点到中心的距离 dA dB dC
	//dA<dB, dA<=dC A 必胜
	//dB<=dA, dB<dC B 必胜
	//dC<dA, dC<=dB C 必胜
	//剩下情况平局
	dfs(A,0);
	if(LCA(B,C)==A)return puts("A"),void();
	dfs(B,0);
	if(LCA(A,C)==B)return puts("B"),void();
	dfs(C,0);
	if(LCA(A,B)==C){
		if(dep[A]==2)return puts("A"),void();
		return puts("C"),void();
	}
	ll o=LCA(A,B);
	ll dA=dep[A]-dep[o],dB=dep[B]-dep[o],dC=dep[o]-1;
	if(dA<dB&&dA<=dC)return puts("A"),void();
	if(dB<=dA&&dB<dC)return puts("B"),void();
	if(dC<dA&&dC<=dB)return puts("C"),void();
	puts("DRAW");
}
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	T=read();
	while(T--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 18228kb

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: 11ms
memory: 18912kb

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

result:

wrong answer 37th lines differ - expected: 'DRAW', found: 'C'