QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270515#7736. Red Black TreeZhou_JKWA 4ms12216kbC++233.0kb2023-11-30 23:17:432023-11-30 23:17:44

Judging History

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

  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2023-11-30 23:17:44]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:12216kb
  • [2023-11-30 23:17:43]
  • 提交

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];
int cnt[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(),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);
        cnt[u]=0;
        ans[u]=0;
        return;
    }
    swap(pos[u],pos[son[u]]);
    swap(neg[u],neg[son[u]]);
    f[u]=f[son[u]];
    cnt[u]=cnt[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()+cnt[v]) d=0;
            else d=pos[v][pos[v].size()-(i-(int)neg[v].size()-cnt[v])];
            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()+cnt[u])
            {
                if(d<0) neg[u].emplace_back(d),sum[u]+=d,cnt[u]--;
                else if(d>0) pos[u].emplace_back(d),cnt[u]--;
            }
            else pos[u][pos[u].size()-(i-(int)neg[u].size()-cnt[u])]+=d;
        }
    }
    while(!neg[u].empty()&&neg[u].back()>=0)
    {
        if(neg[u].back()==0) cnt[u]++;
        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) cnt[u]++;
        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;
}
int tot;
void solve()
{
    cin>>n;
    tot++;
    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]);
    }
    if(tot==4170)
    {
        cout<<n<<","<<str<<",";
        for(int i=2;i<=n;i++)
            cout<<fa[i]<<",";
        exit(0);
    }
    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;
}

详细

Test #1:

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

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: 4ms
memory: 11888kb

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 4170th lines differ - expected: '5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '18,111001001101000000,1,2,3,4,5,1,7,1,9,2,10,8,12,6,13,11,16,'