QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #378379 | #8575. Three Person Tree Game | ucup-team1004# | WA | 14ms | 9524kb | C++14 | 1.4kb | 2024-04-06 12:22:29 | 2024-04-06 12:22:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(T x:a)out<<x<<',';
return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=2e5+10;
int T,n,A,B,C;
vector<int>to[N];
int fa[N],dep[N];
void make(int u,int p=0){
fa[u]=p,dep[u]=dep[p]+1;
for(int v:to[u])if(v^p)make(v,u);
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int x=dep[u]-dep[v];x--;)u=fa[u];
for(;u^v;u=fa[u])v=fa[v];
return u;
}
void get(){
scanf("%d%d%d%d",&n,&A,&B,&C);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
to[u].push_back(v);
to[v].push_back(u);
}
make(A);
int x=LCA(B,C);
int a=dep[x]-dep[A],b=dep[B]-dep[x],c=dep[C]-dep[x];
if(!a){
puts("A");
}else if(!b){
puts("B");
}else if(!c){
if(a==1)puts("A");
else puts("C");
}else if(a<b){
puts("A");
}else if(b<c){
puts("B");
}else if(c+1<a){
puts("C");
}else puts("DRAW");
}
void clr(){
for(int i=1;i<=n;i++)to[i].clear();
}
int main(){
for(scanf("%d",&T);T--;clr())get();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9524kb
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: 14ms
memory: 8476kb
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:
wrong answer 412th lines differ - expected: 'C', found: 'A'