Submission

[PPPPPPPPPP][PPPPP][PPPPPPPP][PPPPPPPPPP]

Score: 100

User: KotatsuCat

Problemset: D.Drunk

Language: cpp

Time: 0.163 second

Submitted On: 2025-01-07 22:21:13

#include<bits/stdc++.h>

using namespace std;

const int mxN = 1e6+1;
int dist1[mxN], dist2[mxN], adj[mxN], wei[mxN], deg[mxN], gp[mxN];
bool vis[mxN];

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> wei[i];
	for(int i=1;i<=n;i++) cin >> adj[i];
	for(int i=1;i<=n;i++){
		if(i==adj[i]) continue;
		deg[adj[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(vis[i] || deg[i]) continue;
		int u = i;
		while(!deg[u]){
			int v = adj[u];
			vis[u] = true;
			dist1[v]=max(dist1[v], dist1[u]+wei[u]);
			--deg[v];
			u = v;
		}
	}
	int id = 0;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int u = i;
		++id;
		while(!vis[u]){
			vis[u] = true;
			gp[u]=id;
			dist2[id]+=wei[u];
			u = adj[u];
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++) ans = max(ans, dist2[gp[i]]+dist1[i]);
	cout << ans;

	return 0;
}