比赛 2025.9.6 评测结果 AAAAAAAAAAAAAAAAAAAAA
题目名称 Bessie s Function 最终得分 100
用户昵称 健康铀 运行时间 1.396 s
代码语言 C++ 内存使用 23.58 MiB
提交时间 2025-09-06 09:21:54
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200010
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
vector <ll> loop[MAXN];
ll cnt,idx;
bool ins[MAXN];
ll fa[MAXN],cst[MAXN],vis[MAXN];
ll dp[MAXN][2],s[MAXN][2];
void build(ll x,ll y){
	nxt[++idx]=hd[x];
	ed[idx]=y;
	hd[x]=idx;
}
queue<ll> q;
void dfs(ll now){
	if(vis[now]==1){
		cnt++;
		for(int i=fa[now];;i=fa[i]){
			loop[cnt].push_back(i);
			ins[i]=true;
			if(i==now)return;
		}
	}else if(vis[now]==2)return;
	else{
		vis[now]=1;
		q.push(now);
		dfs(fa[now]);
	}
}
void dfs_dp(ll now){
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(ins[y])continue;
		dfs_dp(y);
		dp[now][0]+=dp[y][1];
		dp[now][1]+=min(dp[y][0],dp[y][1]);
	} 
	if(fa[now]!=now)dp[now][1]+=cst[now];
}


ll n,ans;
int main(){
	freopen("Function.in","r",stdin);
		freopen("Function.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		fa[i]=read();
		build(fa[i],i);
	}
	for(int i=1;i<=n;i++)cst[i]=read();
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			while(!q.empty()){
				ll now=q.front();
				q.pop();
				vis[now]=2;
			}
		}
	}
//	for(int i=1;i<=cnt;i++){
//		for(int j=0;j<loop[i].size();j++)cout<<loop[i][j]<<" ";
//		cout<<endl;
//	}
	for(int i=1;i<=n;i++)if(ins[i])dfs_dp(i);
//	for(int i=1;i<=n;i++)cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
	for(int i=1;i<=cnt;i++){
		if(loop[i].size()==1){
			ans+=dp[loop[i][0]][1];
			continue;
		}
		ll res=1e9;
		s[0][0]=dp[loop[i][0]][0],s[0][1]=dp[loop[i][0]][1];
		ll sz=loop[i].size()-1;
		for(int j=1;j<=sz;j++){
			ll now=loop[i][j];
			s[j][0]=dp[now][0]+s[j-1][1];
			s[j][1]=dp[now][1]+min(s[j-1][1],s[j-1][0]);
		}
		res=s[sz][1];
		s[0][1]=dp[loop[i][0]][1]+min(dp[loop[i][sz]][0],dp[loop[i][sz]][1]),s[0][0]=dp[loop[i][0]][0]+dp[loop[i][sz]][1];
//			cout<<loop[i][0]<<" "<<s[0][0]<<" "<<s[0][1]<<" "<<dp[loop[i][0]][0]+dp[loop[i][sz]][1]<<endl;
		for(int j=1;j<sz;j++){
			ll now=loop[i][j];
			s[j][0]=dp[now][0]+s[j-1][1];
			s[j][1]=dp[now][1]+min(s[j-1][1],s[j-1][0]);
//			cout<<now<<" "<<s[j][0]<<" "<<s[j][1]<<endl;
		}
		if(sz)res=min(res,s[sz-1][1]);
		ans+=res;
	}
	cout<<ans<<endl;
	return 0;
}