QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378737#8575. Three Person Tree Gameucup-team1055#WA 20ms3584kbC++201.9kb2024-04-06 14:25:572024-04-06 14:25:58

Judging History

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

  • [2024-04-06 14:25:58]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:3584kb
  • [2024-04-06 14:25:57]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end();

using ll = long long;
using ld = long double;
using ull = unsigned long long;

bool chmin(auto &a, auto b) {
    if(a <= b) return false;
    a = b;
    return true;
}

bool chmax(auto &a, auto b) {
    if(a >= b) return false;
    a = b;
    return true;
}

void solve() {
    int n;
    std::cin >> n;
    int a,b,c;
    std::cin >> a >> b >> c;
    a--; b--; c--;
    std::vector g(n, std::vector<int>());
    rep(i,0,n-1) {
        int u,v;
        std::cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    std::vector<int> depth(n, 0), par(n, -1);
    auto dfs = [&](auto &&self, int v) -> void {
        for(auto nv: g[v]) {
            if(nv == par[v]) continue;
            par[nv] = v;
            depth[nv] = depth[v] + 1;
            self(self, nv);
        }
    };
    dfs(dfs, a);
    auto lca = [&](int u, int v) -> int {
        while(depth[u] != depth[v]) {
            if(depth[u] < depth[v]) std::swap(u, v);
            u = par[u];
        }
        while(u != v) {
            u = par[u];
            v = par[v];
        }
        return u;
    };
    int m = lca(b, c);
    depth.assign(n, 0);
    par.assign(n, -1);
    dfs(dfs, m);
    if(depth[a] < depth[b] && depth[a] <= depth[c] + 1) {
        std::cout << "A\n";
    }
    else if(depth[b] < depth[c] && depth[b] <= depth[a] + 1) {
        std::cout << "B\n";
    }
    else if(depth[c] < depth[a] - 1 && depth[c] <= depth[b]) {
        std::cout << "C\n";
    }
    else {
        std::cout << "DRAW\n";
    }
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int t;
    std::cin >> t;
    while(t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 20ms
memory: 3548kb

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'