QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388153#8575. Three Person Tree GameBUET_POTATOES#WA 13ms3872kbC++201.8kb2024-04-13 13:11:222024-04-13 13:11:22

Judging History

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

  • [2024-04-13 13:11:22]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3872kb
  • [2024-04-13 13:11:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int dis[N];
vector<int> adj[N];
int par[N];
void dfs(int ind, int p, int d = 0){
    par[ind] = p;
    dis[ind] = d;
    for(auto x : adj[ind]){
        if(x == p)continue;
        dfs(x, ind, d + 1);
    }
}

int lca(int a, int b){
    while(a != b){
        if(dis[a] > dis[b])a = par[a];
        else b = par[b];
    }
    return a;
}
void testcase(int cs){
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)adj[i].clear();
    int a, b, c;
    cin >> a >> b >> c;

    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }


    for(auto x : adj[a]){
        if(x == c){
            cout << "A\n";
            return;
        }
    }

    dfs(a, -1);

    int l = lca(b, c);

    dfs(l, -1);

    vector<pair<int, int>> v;
    v.emplace_back(dis[a], 0);
    v.emplace_back(dis[b], 1);
    v.emplace_back(dis[c], 2);


    sort(v.begin(), v.end());
    if(v.back().first == v[0].first){
        cout << "DRAW\n";
        return;
    }
    if(dis[a] == dis[c] + 1 && dis[b] == dis[c] + 1){
        cout << "DRAW\n";
        return;
    }
    if(dis[a] == dis[b] + 1 && dis[a] == dis[c] + 1){
        cout << "DRAW\n";
        return;
    }

    string s = "ABC";
    if(v[0].first == v[1].first){
        if((v[0].second + 1) % 3 == v[1].second){
            cout << s[v[1].second] << "\n";
        }else{
            cout << s[v[0].second] << "\n";
        }
        return;
    }
    cout << s[v[0].second] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T = 1;
    cin >> T;
    for(int cs = 1; cs <= T; ++cs){
        testcase(cs);
    }
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 13ms
memory: 3872kb

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

result:

wrong answer 83rd lines differ - expected: 'A', found: 'C'