QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #302673 | #7736. Red Black Tree | mc020207 | WA | 131ms | 51668kb | C++17 | 1.8kb | 2024-01-11 03:29:00 | 2024-01-11 03:29:00 |
Judging History
answer
#include<bits/stdc++.h>
#define MAXN 500010
#define INF 1000000010
#define MOD 998244353
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int v[MAXN];
vector<int> link[MAXN];
int dep[MAXN],son[MAXN],s[MAXN],fa[MAXN];
vector<int> dp[MAXN];
int ans[MAXN];
void dfs(int p){
dep[p]=INF;
son[p]=p;
s[p]=s[fa[p]]+v[p];
for (int q:link[p]){
dfs(q);
dep[p]=min(dep[p],dep[q]+1);
}
if (dep[p]==INF) dep[p]=1;
if (link[p].size()==0){
dp[p].resize(2);
dp[p][0]=v[p]==1;
dp[p][1]=v[p]==0;
ans[p]=0;
return ;
}
if (link[p].size()==1){
son[p]=son[link[p][0]];
ans[p]=ans[son[p]];
return ;
}
dp[p].resize(dep[p]+1);
for (int q:link[p]){
if (link[q].size()!=1){
For(i,0,dep[p]-1){
dp[p][i]+=dp[q][i];
}
}else{
int one=s[fa[son[q]]]-s[fa[q]],num=dep[q]-dep[son[q]];
For(i,0,dep[p]-1){
int dpnow=INF;
For(j,0,dep[son[q]]){
if (j>i) break;
dpnow=min(dpnow,dp[son[q]][j]+abs(i-j-one));
}
dp[p][i]+=dpnow;
}
}
}
if (v[p]==1){
Rof(i,dep[p],1) dp[p][i]=dp[p][i-1];
dp[p][0]=INF;
For(i,0,dep[p]-1) dp[p][i]=min(dp[p][i],dp[p][i+1]+1);
}else{
dp[p][dep[p]]=INF;
Rof(i,dep[p],1) dp[p][i]=min(dp[p][i],dp[p][i-1]+1);
}
ans[p]=INF;
For(i,0,dep[p]) ans[p]=min(ans[p],dp[p][i]);
}
void Main(){
int n;cin>>n;
For(i,1,n){
link[i].clear();
dp[i].clear();
}
string s;cin>>s;
For(i,0,s.size()-1) v[i+1]=s[i]-'0';
For(i,2,n){
int x;cin>>x;
fa[i]=x;
link[x].push_back(i);
}
dfs(1);
For(i,1,n) cout<<ans[i]<<" ";
cout<<"\n";
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;cin>>T;
while (T--) Main();
}
/*
2
9
101011110
1 1 3 3 3 6 2 2
4
1011
1 1 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 34328kb
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: 131ms
memory: 51668kb
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 5838th lines differ - expected: '13 13 13 10 6 6 0 0 0 0 0 0 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '11 11 11 10 6 6 0 0 0 0 0 0 0 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '