QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#286313 | #7736. Red Black Tree | TsReaper | TL | 0ms | 6384kb | C++17 | 2.0kb | 2023-12-17 16:22:18 | 2023-12-17 16:22:18 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
using namespace std;
int n, ans[MAXN + 10];
char s[MAXN + 10];
vector<int> e[MAXN + 10];
struct Magic {
vector<int> neg, pos;
int zero, negSm;
Magic(): zero(0), negSm(0) {};
Magic(vector<int> &vec): zero(0), negSm(0) {
for (int x : vec) {
if (x < 0) neg.push_back(x), negSm += x;
else if (x == 0) zero++;
else pos.push_back(x);
}
reverse(pos.begin(), pos.end());
}
int size() {
return neg.size() + pos.size() + zero;
}
int at(int idx) {
if (idx < neg.size()) return neg[idx];
else if (idx < neg.size() + zero) return 0;
else {
idx -= neg.size() + zero;
return pos[pos.size() - 1 - idx];
}
}
void insert(int x) {
assert(x == 1 || x == -1);
if (x == 1) pos.push_back(1);
else neg.push_back(-1), negSm--;
}
};
typedef pair<int, Magic> pim;
pim dfs(int sn) {
int v = 0;
Magic magic;
for (int fn : e[sn]) {
pim tmp = dfs(fn);
v += tmp.first;
if (magic.size() == 0) magic = tmp.second;
else {
int sz = min(magic.size(), tmp.second.size());
vector<int> vec(sz);
for (int i = 0; i < sz; i++) vec[i] = magic.at(i) + tmp.second.at(i);
magic = Magic(vec);
}
}
v += s[sn] - '0';
if (s[sn] == '0') magic.insert(1);
else magic.insert(-1);
ans[sn] = v + magic.negSm;
return pim(v, magic);
}
void solve() {
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 2; i <= n; i++) {
int x; scanf("%d", &x);
e[x].push_back(i);
}
dfs(1);
for (int i = 1; i <= n; i++) printf("%d%c", ans[i], "\n "[i < n]);
}
int main() {
int tcase; scanf("%d", &tcase);
while (tcase--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6384kb
input:
2 9 101011110 1 1 3 3 3 6 2 2 4 1011 1 1 3
output:
4 1 2 0 0 0 0 0 0 2 0 0 0
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
6107 12 000000001000 1 2 3 2 5 4 4 7 3 8 11 19 1100111101111011110 1 2 1 1 4 5 2 4 3 2 2 7 10 2 11 3 15 5 7 0111110 1 1 2 2 1 5 3 000 1 1 7 1000011 1 2 3 3 5 4 7 0001001 1 1 1 3 5 3 8 00111000 1 1 3 2 5 2 7 11 11111110111 1 1 1 4 5 4 5 2 5 1 15 110101101000010 1 2 3 2 1 5 2 5 6 5 8 7 9 14 10 0101000...
output:
1 1 1 1 0 0 0 0 0 0 0 0 6 2 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 2 1 0 0 0 0 0 0 4 0 0 2 1 0 0 0 0 0 0 4 3 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 6 5 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 5 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 5 3 ...