QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #379013 | #8575. Three Person Tree Game | ucup-team052# | WA | 10ms | 3832kb | C++23 | 1.0kb | 2024-04-06 15:46:44 | 2024-04-06 15:46:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,a,b,c;
vector<int> G[N];
int dep[N],fa[N];
void dfs1(int u,int fa)
{
dep[u]=dep[fa]+1;
::fa[u]=fa;
for(int v:G[u])
{
if(v==fa) continue;
dfs1(v,u);
}
}
int lca(int u,int v)
{
while(dep[u]!=dep[v])
{
if(dep[u]>dep[v]) u=fa[u];
else v=fa[v];
}
while(u!=v) u=fa[u],v=fa[v];
return u;
}
void work()
{
scanf("%d%d%d%d",&n,&a,&b,&c);
for(int i=1;i<=n;i++) G[i].clear(),fa[i]=0,dep[i]=0;
for(int i=1;i<n;i++)
{
int u,v; scanf("%d %d",&u,&v);
G[u].push_back(v),G[v].push_back(u);
}
dfs1(a,0);
int L=lca(b,c);
int da=dep[L]-dep[a],db=dep[b]-dep[L],dc=dep[c]-dep[L];
int wina=(da<db)&&(da<dc+2);
int winb=(db<dc)&&(db<=da);
int winc=(dc<=da-2)&&(dc<=db);
assert(wina+winb+winc<=1);
if(wina) printf("A\n");
else if(winb) printf("B\n");
else if(winc) printf("C\n");
else printf("DRAW\n");
}
signed main()
{
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
int T; cin>>T; while(T--) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3832kb
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: 10ms
memory: 3796kb
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'