QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379169 | #8575. Three Person Tree Game | ucup-team3396# | WA | 11ms | 18912kb | C++14 | 1.9kb | 2024-04-06 16:28:06 | 2024-04-06 16:28:07 |
Judging History
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'