P1043 区间 DP WA on #3 #4 #5 #6求调
查看原帖
P1043 区间 DP WA on #3 #4 #5 #6求调
543555
_Emperorpenguin_楼主2024/10/23 21:17

RT。

#include <bits/stdc++.h>
#pragma GCC optmize(2)
using namespace std;

int n,x; 
vector<int> e[1005];
int v0[1005],v1[1005],v2[1005],ans;
int f[1005];
priority_queue<pair<int,int> > q;

void depth(int u,int fa,int d){
	q.push(make_pair(d,u));
	f[u]=fa;
	for(int i=0;i<e[u].size();i++)
		if(e[u][i]!=fa)
			depth(e[u][i],u,d+1);
	return;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>x;
		e[i].push_back(x);
		e[x].push_back(i);
	}
	depth(1,0,1);
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
//		cout<<u<<" "<<f[u]<<" "<<f[f[u]]<<endl;
		if(v0[u]||v1[u]||v2[u]||v0[f[u]]||v1[f[u]]||v0[f[f[u]]]) continue;
		ans++;
		v2[u]=1;
		v1[f[u]]=1;
		v0[f[f[u]]]=1;
	}
	cout<<ans;
	return 0;
}

2024/10/23 21:17
加载中...