QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#572027 | #8948. 报复社会 | JWRuixi | 0 | 2ms | 10008kb | C++20 | 1.3kb | 2024-09-18 11:14:52 | 2024-09-18 11:14:52 |
Judging History
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%