QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#572027#8948. 报复社会JWRuixi0 2ms10008kbC++201.3kb2024-09-18 11:14:522024-09-18 11:14:52

Judging History

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

  • [2024-09-18 11:14:52]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:10008kb
  • [2024-09-18 11:14:52]
  • 提交

answer

#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 5e5 + 9;
int n, a[N], p[N], d[N];
vi g[N];

void dfs (int u, int f) {
  d[u] = 0;
  for (int v : g[u]) {
    if (g[v].empty()) {
      d[u] += 1 - 2 * a[v];
    }
  }
  vi w;
  for (int v : g[u]) {
    if (sz(g[v])) {
      dfs(v, u);
      w.eb(d[v]);
    }
  }
  sort(w.begin(), w.end());
  int l = 0, r = sz(w) - 1;
  while (l <= r) {
    if (d[u] <= 0) {
      d[u] += 1 + w[r--];
    } else {
      d[u] += -1 + w[l++];
    }
  }
}

void slv () {
  cin >> n;
  L (i, 2, n) {
    cin >> p[i];
    g[p[i]].eb(i);
  }
  L (i, 1, n) {
    cin >> a[i];
  }
  if (n == 1) {
    cout << (a[1] ? "Bob" : "Alice") << '\n';
    return;
  }
  dfs(1, 0);
  cout << (a[1] > 0 ? "Alice" : "Bob") << '\n';
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    slv();
  }
}
// I love WHQ!

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 2ms
memory: 9752kb

input:

1
19
1 2 3 3 2 6 7 7 6 6 6 2 2 2 1 1 1 1
0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0

output:

Bob

result:

ok "Bob"

Test #2:

score: 20
Accepted
time: 0ms
memory: 10008kb

input:

1
20
1 1 3 2 4 1 4 4 1 7 1 6 3 12 6 12 8 5 7
1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1

output:

Alice

result:

ok "Alice"

Test #3:

score: 0
Wrong Answer
time: 2ms
memory: 9984kb

input:

1
19
1 2 3 4 5 1 1 8 8 3 7 3 13 3 15 10 2 17
0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0

output:

Bob

result:

wrong answer 1st words differ - expected: 'Alice', found: 'Bob'

Subtask #2:

score: 0
Time Limit Exceeded

Test #50:

score: 0
Time Limit Exceeded

input:

10000
49
1 2 2 1 5 5 5 5 5 5 1 12 12 12 12 12 12 1 19 19 19 19 19 19 19 1 27 27 1 1 31 1 33 33 33 33 33 33 33 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1
50
1 2 2 2 2 2 1 8 8 8 1 12 1 1 15 15 15 15 1 1 21 21 21 21 1 26 1 1 29 29...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #73:

score: 0
Time Limit Exceeded

input:

10000
50
1 2 1 4 5 6 5 4 9 4 11 4 1 14 15 16 16 16 15 14 21 21 21 14 14 14 14 14 1 30 30 30 30 30 1 36 37 37 37 36 41 41 41 36 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1
50
1 2 3 4 5 4 7 8 7 4 11 12 11 14 11 16 11 18 11 4 21 4 4 4 3 ...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%