比赛 |
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;
}