Submission

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

Score: 30

User: KotatsuCat

Problemset: D.Drunk

Language: cpp

Time: 0.582 second

Submitted On: 2025-01-07 20:47:53

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

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

void dfs(int u, int p){
	vis[u] = true;
	int mx = 0;
	for(int &v:g[u]){
		if(v==p || deg[v]) continue;
		dfs(v, u);
		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] || vis[i]) continue;
		int u = i;
		while(!deg[u]){
			int v = adj[u];
			deg[v]--;
			vis[u] = true;
			u = v;
		}
	}
	fill(vis, vis+n+1, false);
	int id = 0;
	for(int i=1;i<=n;i++){
		if(vis[i] || !deg[i]) continue;
		int u = i;
		++id;
		while(!vis[u]){
			int v = adj[u];
			--deg[v];
			gp[u]=id;
			dist1[gp[u]]+=wei[u];
			vis[u] = true;
			u = v;
		}
	}
	for(int i=1;i<=n;i++) if(deg[i]) wei[i]=0, dfs(i, -1);
	int ans = 0;
	for(int i=1;i<=n;i++) ans = max(ans, dist1[gp[i]]+wei[i]);
	cout << ans;

	return 0;
}