QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381550#8575. Three Person Tree Gameucup-team004#WA 7ms7820kbC++201.7kb2024-04-07 18:50:102024-04-07 18:50:10

Judging History

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

  • [2024-04-07 18:50:10]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:7820kb
  • [2024-04-07 18:50:10]
  • 提交

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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7820kb

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: 5656kb

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'