QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287972 | #7736. Red Black Tree | ucup-team045 | WA | 335ms | 42904kb | C++20 | 5.0kb | 2023-12-21 13:32:45 | 2023-12-21 13:32:46 |
Judging History
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 p;
}
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 t1 = kth(root[j], k);
int t2 = kth(root[u], k);
tr[t2].key += tr[t1].key;
pull(t2);
}
// 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);
}
// 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;
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: 1ms
memory: 7832kb
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: 335ms
memory: 42904kb
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'