Submission

[-SSSSSSSSS][-SSSS][-SSSSSSS][-SSSSSSSSS]

Score: 0

User: KotatsuCat

Problemset: D.Drunk

Language: cpp

Time: 0.027 second

Submitted On: 2025-01-07 20:59:39

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

#define ll long long

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

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

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]) {
            g[adj[i]].emplace_back(i);
            deg[adj[i]]++;
        }
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) q.push(i);
    }

    // Topological sorting to resolve non-cyclic components
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int v = adj[u];
        deg[v]--;
        if (deg[v] == 0) q.push(v);
    }

    int ans = 0;
    memset(vis, 0, sizeof(vis));

    // Process cyclic components and calculate the maximum weight
    for (int i = 1; i <= n; i++) {
        if (vis[i] || deg[i] == 0) continue;
        int u = i, cycle_sum = 0, max_weight = 0;

        // Traverse and calculate cycle sum
        do {
            cycle_sum += wei[u];
            vis[u] = 1;
            u = adj[u];
        } while (u != i);

        // Traverse again to calculate max path in the cycle
        do {
            dfs(u, max_weight);
            u = adj[u];
        } while (u != i);

        ans = max(ans, cycle_sum + max_weight);
    }

    // Process remaining acyclic components
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            int max_weight = 0;
            dfs(i, max_weight);
            ans = max(ans, max_weight);
        }
    }

    cout << ans << '\n';
    return 0;
}