QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380531#8575. Three Person Tree Gameucup-team1766#WA 13ms3620kbC++171.3kb2024-04-07 05:32:222024-04-07 05:32:23

Judging History

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

  • [2024-04-07 05:32:23]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3620kb
  • [2024-04-07 05:32:22]
  • 提交

answer

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

void dfs(vector<int> tree[], vector<int> &par, int cur, int prev) {
  par[cur] = prev;
  for (int nei : tree[cur]) {
    if (nei != prev) {
      dfs(tree, par, nei, cur);
    }
  }
}

void solve() {
  int N;
  cin >> N;
  int a, b, c;
  cin >> a >> b >> c;
  a--; b--; c--;
  
  vector<int> tree[N];
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }

  vector<int> par(N);
  dfs(tree, par, a, -1);

  vector<int> marks(N, -1);
  int cur = b;
  int cnt = 0;
  while (cur != -1) {
    marks[cur] = cnt;
    cur = par[cur];
    cnt++;
  }

  cur = c;
  cnt = 0;
  int adist, bdist, cdist, center;
  while (cur != -1) {
    if (marks[cur] >= 0) {
      bdist = marks[cur];
      cdist = cnt;
      center = cur;
      break;
    }
    cur = par[cur];
    cnt++;
  }

  cur = center;
  adist = 0;
  while (cur != a) {
    adist++;
    cur = par[cur];
  }

  if (adist < bdist && adist - 1 <= cdist) {
    cout << "A\n";
  } else if (bdist <= adist && bdist < cdist) {
    cout << "B\n";
  } else if (cdist <= bdist && cdist < adist - 1) {
    cout << "C\n";
  } else {
    cout << "DRAW\n";
  }
}

int main() {  
  cin.tie(0)->sync_with_stdio(0);
  int T; cin >> T; while (T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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'