QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#286315 | #7736. Red Black Tree | TsReaper | TL | 1937ms | 52208kb | C++17 | 2.0kb | 2023-12-17 16:23:29 | 2023-12-17 16:23:30 |
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 = move(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: 6208kb
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: 0
Accepted
time: 1937ms
memory: 52208kb
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 ...
result:
ok 6107 lines
Test #3:
score: 0
Accepted
time: 313ms
memory: 9728kb
input:
10 100000 10001010000001100001000100001000010100010101100001001110110001000010000110001000000010000011000001000001010001110100000000000000000010011011100000000000001000000000100100100110000000100001010011000000110000000111010100100001100000100100101001000000010000000011100000000000000010001100011100...
output:
22440 21414 19422 13454 5328 2719 1421 1168 1478 661 4662 5037 418 183 2304 501 2008 1643 692 2211 570 1003 967 950 504 124 894 333 775 523 905 197 12 337 195 310 1325 1016 638 50 907 361 179 336 313 102 309 555 733 871 490 414 375 318 66 625 336 267 276 162 203 25 112 216 252 146 42 233 232 333 27 ...
result:
ok 10 lines
Test #4:
score: 0
Accepted
time: 156ms
memory: 7024kb
input:
10 100000 01010111111101011100011111111010011001111111110001100111111101011111110011101111110110111011010111011011010011111110101111111011111111011101011111011001110101111011011010110100011111001101001011111101111101111111111100101101000111111110111101111111111011111100111011101110110101111010101101...
output:
25019 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 10 lines
Test #5:
score: -100
Time Limit Exceeded
input:
10 100000 00111110110011111111111010011111011111101010110111111110011110111111111111000110101110110111111101011111111111010101111111011001110110011101111001110111101101110110101000011111110100101110110100111110001111011100111101011010111111011011100011111011110111111110011110111111001111111010011100...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...