QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379732#8575. Three Person Tree Gameucup-team206#WA 18ms15516kbC++172.1kb2024-04-06 18:37:312024-04-06 18:37:31

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 18:37:31]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:15516kb
  • [2024-04-06 18:37:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+1e3+7;

int T,n,pos[3];

vector<int> g[N];

int mn[N*2][21],anc[N][21];

int seq[N],dc,st[N],fa[N],dep[N];

void dfs(int x,int f)
{
    anc[x][0]=f;
    for(int j=1;j<=20;j++)
        anc[x][j]=anc[anc[x][j-1]][j-1];
    dep[x]=dep[f]+1;
    fa[x]=f;
    seq[++dc]=x;
    st[x]=dc;
    mn[dc][0]=st[x];
    for(auto v:g[x])
    {
        if(v==f)
            continue;
        dfs(v,x);
        seq[++dc]=x; 
        mn[dc][0]=st[x];
    }
}

int lca(int x,int y)
{
    x=st[x],y=st[y];
    if(x>y)
        swap(x,y);
    int k=__lg(y-x+1);
    return seq[min(mn[x][k],mn[y-(1<<k)+1][k])];
}

int find(int x,int y)
{
    int p=lca(x,y);
    if(p!=x)
        return fa[x];
    else
    {
        int t=dep[y]-dep[x]-1;
        while(t)
        {
            int k=__builtin_ctz(t);
            t-=1<<k;
            y=anc[y][k];
        }
        return y;
    }
}

int go(int t)
{
    int x=pos[t],y=pos[(t+2)%3];
    int p=find(x,y);
    int z=pos[(t+1)%3];
    if(p==z||p==fa[z]||z==fa[p])
        return x;
    return p;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<3;i++)
            cin>>pos[i];
        for(int i=1;i<=n;i++)
            g[i].clear();
        for(int i=1;i<n;i++)
        {
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dc=0;
        dfs(1,0);
        for(int j=1;j<=20;j++)
            for(int i=1;i+(1<<j)-1<=dc;i++)
                mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        // cout<<i<<" "<<j<<" "<<lca(i,j)<<endl;
        // cout<<lca(2,5)<<"\n";
        int t=0;
        int round=n*3+10;
        while(round--)
        {
            int p=go(t);
            pos[t]=p;
            if(pos[t]==pos[(t+2)%3])
            {
                cout<<"ABC"[t]<<"\n";
                break;
            }
            t=(t+1)%3;
        }
        if(round<0)
            cout<<"DRAW\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14928kb

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: 18ms
memory: 15516kb

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
C
B
A
A
A
B
B
B
C
A
A
A
B
B
DRAW
C
DRAW
A
A
C
A
A
B
B
C
C
DRAW
A
B
C
B
DRAW
A
C
DRAW
C
B
C
DRAW
DRAW
A
A
C
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
C
B
B
B
A
A
B
B
A
C
DRAW
B
A
B
C
A
A
C
A
A
DRAW
A
A
C
C
DRAW
C
A
B
A...

result:

wrong answer 21st lines differ - expected: 'A', found: 'C'