QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270530#7736. Red Black TreeZhou_JKWA 210ms43432kbC++233.2kb2023-12-01 00:09:172023-12-01 00:09:18

Judging History

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

  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-12-01 00:09:18]
  • 评测
  • 测评结果:WA
  • 用时:210ms
  • 内存:43432kb
  • [2023-12-01 00:09:17]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int N=100005;
int n;
int c[N];
int fa[N];
vector<int>G[N];
int dis[N],dep[N],son[N],len[N];
void init(int u,int father)
{
    dis[u]=dep[u]=dep[father]+1;
    son[u]=0;
    for(int v:G[u])
    {
        if(v==father) continue;
        init(v,u);
        if(son[u]==0||dis[v]<dis[son[u]]) son[u]=v;
    }
    if(son[u]) dis[u]=dis[son[u]];
    len[u]=dis[u]-dep[u]+1;
    return;
}
int f[N];
vector<int>pos[N],neg[N],zero[N];
int ans[N];
long long sum[N];
void dfs(int u,int father)
{
    if(son[u]) dfs(son[u],u);
    else
    {
        pos[u].clear(),zero[u].clear(),neg[u].clear();
        if(c[u]==0) f[u]=0,sum[u]=0,pos[u].emplace_back(1);
        else f[u]=1,sum[u]=-1,neg[u].emplace_back(-1);
        ans[u]=0;
        return;
    }
    swap(pos[u],pos[son[u]]);
    swap(zero[u],zero[son[u]]);
    swap(neg[u],neg[son[u]]);
    f[u]=f[son[u]];
    sum[u]=sum[son[u]];
    for(int v:G[u])
    {
        if(v==father||v==son[u]) continue;
        dfs(v,u);
        f[u]+=f[v];
        for(int i=1;i<len[u];i++)
        {
            int d=0;
            if(i<=(int)neg[v].size()) d=neg[v][i-1];
            else if(i<=(int)neg[v].size()+(int)zero[v].size()) d=0;
            else d=pos[v][pos[v].size()-(i-(int)neg[v].size()-(int)zero[v].size())];
            if(d==0) continue;
            if(i<=(int)neg[u].size()) neg[u][i-1]+=d,sum[u]+=d;
            else if(i<=(int)neg[u].size()+(int)zero[u].size()) zero[u][i-(int)neg[u].size()-1]+=d;
            else pos[u][pos[u].size()-(i-(int)neg[u].size()-(int)zero[u].size())]+=d;
        }
    }
    int tot=0;
    for(int i=0;i<(int)zero[u].size()&&zero[u][i]<0;i++)
        sum[u]+=zero[u][i],neg[u].emplace_back(zero[u][i]),tot++;
    for(int i=(int)zero[u].size()-1;i>=0&&zero[u][i]>0;i--)
        pos[u].emplace_back(zero[u][i]),tot++;
    zero[u].resize(zero[u].size()-tot);
    while(!neg[u].empty()&&neg[u].back()>=0)
    {
        if(neg[u].back()==0) zero[u].emplace_back(0);
        else pos[u].emplace_back(neg[u].back());
        sum[u]-=neg[u].back();
        neg[u].pop_back();
    }
    while(!pos[u].empty()&&pos[u].back()<=0)
    {
        if(pos[u].back()==0) zero[u].emplace_back(0);
        else sum[u]+=pos[u].back(),neg[u].emplace_back(pos[u].back());
        pos[u].pop_back();
    }
    if(c[u]==0) pos[u].emplace_back(1);
    else f[u]++,neg[u].emplace_back(-1),sum[u]+=-1;
    ans[u]=f[u]+sum[u];
    return;
}
void solve()
{
    cin>>n;
    string str;
    cin>>str;
    for(int i=1;i<=n;i++)
        c[i]=str[i-1]-'0';
    for(int i=1;i<=n;i++)
        G[i].clear();
    for(int i=2;i<=n;i++)
    {
        cin>>fa[i];
        G[fa[i]].emplace_back(i);
        G[i].emplace_back(fa[i]);
    }
    init(1,0);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

/*
1
18
111001001101000000
1 2 3 4 5 1 7 1 9 2 10 8 12 6 13 11 16
*/

詳細信息

Test #1:

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

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: 210ms
memory: 43432kb

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

result:

wrong answer 5816th lines differ - expected: '8 8 8 7 0 0 0 0 0 0 0 0 0 0 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '6 6 8 7 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '