QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287987 | #7736. Red Black Tree | ucup-team045 | Compile Error | / | / | C++20 | 4.7kb | 2023-12-21 14:00:19 | 2024-02-19 10:15:55 |
Judging History
你现在查看的是最新测评结果
- [2024-02-19 10:15:55]
- 自动重测本题所有获得100分的提交记录
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2024-02-19 10:14:05]
- hack成功,自动添加数据
- (/hack/538)
- [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()); | ^~~~~~~