QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302673#7736. Red Black Treemc020207WA 131ms51668kbC++171.8kb2024-01-11 03:29:002024-01-11 03:29:00

Judging History

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

  • [2024-02-19 10:14:05]
  • hack成功,自动添加数据
  • (/hack/538)
  • [2024-01-11 03:29:00]
  • 评测
  • 测评结果:WA
  • 用时:131ms
  • 内存:51668kb
  • [2024-01-11 03:29:00]
  • 提交

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
*/

详细

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 '