QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287987#7736. Red Black Treeucup-team045Compile Error//C++204.7kb2023-12-21 14:00:192024-02-19 10:15:55

Judging History

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

  • [2024-02-19 10:15:55]
  • 自动重测本题所有获得100分的提交记录
  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-12-21 14:00:20]
  • 评测
  • 测评结果:100
  • 用时:648ms
  • 内存:54064kb
  • [2023-12-21 14:00:19]
  • 提交

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, tr[root[j]].size);
    }
    {
        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];
        auto [x, y] = split_at(root[j], mn);
        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);
    }
}

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];
        }
    }

}

詳細信息

answer.code: In function ‘void dfs2(int)’:
answer.code:161:9: error: ‘reverse’ was not declared in this scope
  161 |         reverse(v.begin(), v.end());
      |         ^~~~~~~