QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#270515 | #7736. Red Black Tree | Zhou_JK | WA | 4ms | 12216kb | C++23 | 3.0kb | 2023-11-30 23:17:43 | 2023-11-30 23:17:44 |
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;
}
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,'