QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #381533 | #8575. Three Person Tree Game | ucup-team004# | WA | 7ms | 7664kb | C++20 | 1.7kb | 2024-04-07 18:39:02 | 2024-04-07 18:39:02 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 300005,K=20;
constexpr int P = 998244353;
using namespace std;
vector<int> v[N];
int n,A[3],B[3],dep[N],fa[N];
#define For(i,l,r) for(int i=l;i<=(int)(r);i++)
#define pb push_back
int lca(int x,int y){
static int vis[N];
For(i,1,n)vis[i]=0;
for(int i=x;i;i=fa[i]){vis[i]=1;}
for(int i=y;i;i=fa[i])if(vis[i])return i;
assert(0);
}
void dfs(int p){
//cerr<<p<<" "<<fa[p]<<endl;
dep[p]=dep[fa[p]]+1;
for(auto i:v[p])if(i!=fa[p]){
fa[i]=p;
dfs(i);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
cin>>T;
while(T--){
cin>>n;
For(i,1,n)v[i].clear();
For(i,0,2)cin>>A[i];
For(i,1,n-1){
int s,t;
cin>>s>>t;
v[s].pb(t);
v[t].pb(s);
}
fa[A[0]]=0;
dfs(A[0]);
int x=lca(A[1],A[2]);
B[0]=dep[x]-dep[A[0]];
B[1]=dep[A[1]]-dep[x];
B[2]=dep[A[2]]-dep[x];
//cerr<<B[0]<<" "<<B[1]<<" "<<B[2]<<"\n";
int fl=1;
For(o,0,2){
int cnt=0;
For(oo,0,2)if(oo!=o){
cnt+=(B[oo]-B[o]>=(o<oo?0:1)+((o+1)%3==oo?-1:1));
//if(o==0)cerr<<B[oo]-B[o]<<" "<<(o<oo?0:1)+((o+1)%3==oo?-1:1)<<endl;
}
if(cnt==2){
fl=0;
if(o==0)cout<<"A"<<endl;
else if(o==1)cout<<"B"<<endl;
else cout<<"C"<<endl;
break;
}
}
if(fl)cout<<"DRAW"<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7652kb
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: 7ms
memory: 7664kb
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 B B B A DRAW A DRAW DRAW DRAW DRAW DRAW A A C A A B A C A A A A B DRAW C DRAW A A DRAW C C A DRAW DRAW C DRAW A A DRAW B DRAW A B DRAW DRAW DRAW C DRAW DRAW A A DRAW DRAW DRAW B B B A DRAW B A A A DRAW B A A DRAW DRAW C A C DRAW DRAW A B A A DRAW A B B A A B DRAW A C DRAW A...
result:
wrong answer 11th lines differ - expected: 'C', found: 'B'