Submission

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

Score: 30

User: KotatsuCat

Problemset: D.Drunk

Language: cpp

Time: 0.681 second

Submitted On: 2025-01-07 22:04:53

#include<bits/stdc++.h>

using namespace std;

const int mxN = 1e6+1;
int adj[mxN], wei[mxN];
vector<int> g[mxN];
int dist1[mxN], deg[mxN], gp[mxN];

void dfs(int u){
	int mx = 0;
	gp[u]=gp[u]?gp[u]:-1;
	for(int &v:g[u]){
		if(gp[v]) continue;
		dfs(v);
		mx = max(mx, wei[v]);
	}
	wei[u]+=mx;
}

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;
		g[adj[i]].emplace_back(i);
		deg[adj[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(deg[i] || gp[i]) continue;
		int u = i;
		while(!deg[u]){
			int v = adj[u];
			deg[v]--;
			gp[u]=1;
			u = v;
		}
	}
	fill(gp+1, gp+n+1, 0);
	int id = 0;
	for(int i=1;i<=n;i++){
		if(gp[i] || !deg[i]) continue;
		int u = i;
		++id;
		while(!gp[u]){
			int v = adj[u];
			gp[u]=id;
			dist1[gp[u]]+=wei[u];
			u = v;
		}
	}
	for(int i=1;i<=n;i++) if(deg[i]) wei[i]=0, dfs(i);
	int ans = 0;
	for(int i=1;i<=n;i++) ans = max(ans, dist1[max(gp[i], 0)]+wei[i]);
	// {
	// 	int i = 1;
	// 	cerr << gp[i] << " " << dist1[max(gp[i], 0)] << " " << wei[i] << "\n";
	// }
	cout << ans;

	return 0;
}