QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286315#7736. Red Black TreeTsReaperTL 1937ms52208kbC++172.0kb2023-12-17 16:23:292023-12-17 16:23:30

Judging History

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

  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-12-17 16:23:30]
  • 评测
  • 测评结果:TL
  • 用时:1937ms
  • 内存:52208kb
  • [2023-12-17 16:23:29]
  • 提交

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 ...

result: