QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379296 | #8575. Three Person Tree Game | ucup-team266# | WA | 42ms | 17932kb | C++23 | 2.3kb | 2024-04-06 16:58:39 | 2024-04-06 16:58:39 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[200200];
int anc[19][200200];
int depth[200200];
void dfs(int u,int fa)
{
depth[u]=depth[fa]+1;
anc[0][u]=fa;
for(auto v:G[u])
if(v!=fa)
dfs(v,u);
}
int lca(int u,int v)
{
for(int i=18;i>=0;i--)
{
if(depth[anc[i][u]]>=depth[v])
u=anc[i][u];
if(depth[anc[i][v]]>=depth[u])
v=anc[i][v];
}
if(u==v) return u;
for(int i=18;i>=0;i--)
if(anc[i][u]!=anc[i][v])
{
u=anc[i][u];
v=anc[i][v];
}
return anc[0][u];
}
int dist(int u,int v)
{
return depth[u]+depth[v]-2*depth[lca(u,v)];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
G[i].clear();
int a,b,c;
cin>>a>>b>>c;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
dfs(1,0);
for(int i=1;i<19;i++)
for(int j=1;j<=n;j++)
anc[i][j]=anc[i-1][anc[i-1][j]];
int rt=1;
int sm=inf;
for(int i=1;i<=n;i++)
{
int sum=dist(i,a)+dist(i,b)+dist(i,c);
if(sum<sm)
{
sm=sum;
rt=i;
}
}
int dA=dist(a,rt),dB=dist(b,rt),dC=dist(c,rt);
int mn=min({dA,dB,dC});
if(max({dA,dB,dC})==mn)
puts("DRAW");
else if(dA==mn&&dB==mn)
puts("B");
else if(dA==mn&&dC==mn)
puts("A");
else if(dB==mn&&dC==mn)
{
if(dA==mn+1)
puts("DRAW");
else
puts("C");
}
else if(dA==mn)
puts("A");
else if(dB==mn)
puts("B");
else
{
assert(dC==mn);
if(dA==mn+1)
{
if(dB==mn+1)
puts("DRAW");
else
puts("A");
}
else
puts("C");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 17908kb
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: 42ms
memory: 17932kb
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'