Submission

Score: 100

User: Seng

Problemset: D.Drunk

Language: cpp

Time: 0.282 second

Submitted On: 2026-03-20 19:18:26

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin >> n;
    vector<int> x(n+1, 0), d(n+1, 0);
    vector<vector<int>> go_to(n+1);
    queue<pii> q;
    int ans = 0;
    for(int i = 1; i <= n; i++) cin >> d[i];
    for(int i = 1; i <= n; i++){
        cin >> x[i];
        if(x[i] == i){
            q.push({i, d[i]});
            ans = max(ans, d[i]);
        }
        go_to[x[i]].push_back(i);
    }
    // for(int i = 1; i <= n; i++){
    //     cout << "go_to[" << i << "] -> ";
    //     for(auto e : go_to[i]) cout << e << " ";
    //     cout << '\n';
    // }
    
    while(!q.empty()){
        auto [i, v] = q.front();
        q.pop();

        for(auto e  : go_to[i]){
            if(e == i) continue;
            
            if(go_to[e].empty()) ans = max(ans, v+d[e]);
            else q.push({e, v+d[e]});
        }
    }
    //cout << '\n';
    cout << ans;

    return 0;
}

/*
8
3 3 4 8 5 4 4 6
6 2 2 6 4 6 6 3 

10
9 15 8 6 9 2 11 18 20 9
1 1 1 10 7 1 6 10 4 3


*/