QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#270514 | #7736. Red Black Tree | Zhou_JK | WA | 203ms | 39548kb | C++23 | 2.8kb | 2023-11-30 23:15:14 | 2023-11-30 23:15:14 |
Judging History
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;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12324kb
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: 203ms
memory: 39548kb
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: '4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '