Submission

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

Score: 100

User: chawinkn

Problemset: D.Drunk

Language: cpp

Time: 0.799 second

Submitted On: 2025-04-04 18:40:10

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>

int d[1000009], dist[1000009];
vector<pii> g[1000009];
priority_queue<pii,vector<pii>,greater<pii>> pq;
bool visited[1000009];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> d[i];
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (i == x) pq.push({dist[i]=d[i], i});
		else g[x].push_back({i, d[i]});
	}
	int ans=0;
	while (!pq.empty()) {
		auto [D,u]=pq.top(); pq.pop();
		if (visited[u]) continue;
		visited[u] = true;
		ans = max(ans, D);
		for (auto [v,w] : g[u]) {
			if (D+w > dist[v]) pq.push({dist[v]=D+w, v});
		}
	}
	cout << ans;
	return 0;
}