QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287983#7736. Red Black Treeucup-team045WA 476ms48884kbC++205.0kb2023-12-21 13:51:402023-12-21 13:51:41

Judging History

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

  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-12-21 13:51:41]
  • 评测
  • 测评结果:WA
  • 用时:476ms
  • 内存:48884kb
  • [2023-12-21 13:51:40]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<limits>
#include<random>
#include<cassert>
using namespace std;
using LL = long long;

mt19937 rnd(random_device{}());
uniform_int_distribution<int> dist(0, 1000'000'000);

const int maxn = 1e5 + 5;
struct Node{
    int key, sum;
    int l, r, prior, size;
}tr[maxn * 32];
int idx;

int new_node(int key){
    tr[++idx].key = key;
    tr[idx].sum = key;
	tr[idx].l = tr[idx].r = 0; 
    tr[idx].prior = dist(rnd);
    tr[idx].size = 1;
    return idx;
}

void pull(int u){
    tr[u].sum = tr[tr[u].l].sum + tr[u].key + tr[tr[u].r].sum;
    tr[u].size = tr[tr[u].l].size + 1 + tr[tr[u].r].size;
}

pair<int, int> split(int p, int key){
    if (!p) return {0, 0};
    if (tr[p].key <= key){
        auto [x, y] = split(tr[p].r, key);
        tr[p].r = x;
        pull(p);
        return {p, y};
    }
    else{
        auto [x, y] = split(tr[p].l, key);
        tr[p].l = y;
        pull(p);
        return {x, p};
    }
}

pair<int, int> split_at(int p, int size){
    if (!p) return {0, 0};
    if (tr[tr[p].l].size < size){
        auto [x, y] = split_at(tr[p].r, size - tr[tr[p].l].size - 1);
        tr[p].r = x;
        pull(p);
        return {p, y};
    }
    else{
        auto [x, y] = split_at(tr[p].l, size);
        tr[p].l = y;
        pull(p);
        return {x, p};
    }
}

int merge(int x, int y){
    if (x == 0 || y == 0) return x + y;
    if (tr[x].prior > tr[y].prior){
        tr[x].r = merge(tr[x].r, y);
        pull(x);
        return x;
    }
    else{
        tr[y].l = merge(x, tr[y].l);
        pull(y);
        return y;
    }
}

int type[maxn], root[maxn], tag[maxn];
vector<int> g[maxn];
int ans[maxn], len[maxn];

void dfs1(int u){
    len[u] = 1;
    for(auto &j : g[u]){
        dfs1(j);
        len[u] = max(len[u], len[j] + 1);
        if (len[j] > len[g[u][0]]) swap(j, g[u][0]);
    }
}

void collect(int u, vector<int> &v){
    if (tr[u].l) collect(tr[u].l, v);
    v.push_back(tr[u].key);
    if (tr[u].r) collect(tr[u].r, v);
}

void update(int u, vector<int> &v){
    if (tr[u].l) update(tr[u].l, v);
    tr[u].key += v.back();
    v.pop_back();
    if (tr[u].r) update(tr[u].r, v);
    pull(u);
}

void print(int u, int &v){
    if (tr[u].l) print(tr[u].l, v);
    v += tr[u].key;
    cout << v << ' ';
    if (tr[u].r) print(tr[u].r, v);
}

int kth(int p, int k){
    while(p){
        if (tr[tr[p].l].size >= k){
            p = tr[p].l;
        }
        else if (tr[tr[p].l].size + 1 >= k){
            break;
        }
        else{
            k -= tr[tr[p].l].size + 1;
            p = tr[p].r;
        }
    }
    return tr[p].key;
}

void dfs2(int u){
    if (g[u].empty()){
        ans[u] = 0;
        if (type[u]){
            tag[u] += 1;
            root[u] = new_node(-1);
        }
        else{
            root[u] = new_node(1);
        }
        // cout << u << '\n';
        // int v = tag[u];
        // print(root[u], v);
        // cout << '\n';
        return;
    }
    int mn = 1e9;
    for(auto j : g[u]){
        dfs2(j);
        tag[u] += tag[j];
        mn = min(mn, len[j]);
    }
    {
        auto [x, y] = split_at(root[g[u][0]], mn);
        root[u] = x;
    }
    for(int i = 1; i < g[u].size(); i++){
        int j = g[u][i];
        for(int k = 1; k <= mn; k++){
            int v = kth(root[j], k);
            auto [x, t] = split_at(root[u], k - 1);
            auto [y, z] = split_at(t, 1);
            tr[y].key += v;
            tr[y].sum += v;
            root[u] = merge(merge(x, y), z);
        }
        // vector<int> v;
        // collect(x, v);
        // reverse(v.begin(), v.end());
        // update(root[u], v);
    }
    if (type[u]){
        tag[u] += 1;
        auto [x, y] = split(root[u], -1);
        root[u] = merge(merge(x, new_node(-1)), y);
    }
    else{
        auto [x, y] = split(root[u], 1);
        root[u] = merge(merge(x, new_node(1)), y);
    }
    {
        auto [x, y] = split(root[u], 0);
        ans[u] = tag[u] + tr[x].sum;
        root[u] = merge(x, y);
    }
    // cout << u << '\n';
    // int v = tag[u];
    // print(root[u], v);
    // cout << '\n';
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            g[i].clear();
            ans[i] = 0;
            root[i] = 0;
            len[i] = 0;
            tag[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            char c;
            cin >> c;
            type[i] = c - '0';
        }
        for(int i = 2; i <= n; i++){
            int x;
            cin >> x;
            g[x].push_back(i);
        }
        dfs1(1);
        dfs2(1);
        for(int i = 1; i <= n; i++){
            cout << ans[i] << " \n"[i == n];
        }
    }

}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 6812kb

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
Wrong Answer
time: 476ms
memory: 48884kb

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:

wrong answer 40th lines differ - expected: '3 3 1 0 1 1 1 1 0 0 0 0 0 0 0 0', found: '2 2 1 0 1 1 1 1 0 0 0 0 0 0 0 0'