QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286313#7736. Red Black TreeTsReaperTL 0ms6384kbC++172.0kb2023-12-17 16:22:182023-12-17 16:22:18

Judging History

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

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

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

result: