fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int n;
  6. vector<int> a, c;
  7. vector<array<ll, 2>> dp;
  8. vector<vector<int>> adj, radj;
  9. vector<bool> cycle;
  10.  
  11. void calcdp(int i) {
  12.     for (int j: radj[i]) {
  13.         calcdp(j);
  14.         dp[i][0] += dp[j][1];
  15.         dp[i][1] += min(dp[j][0], dp[j][1]);
  16.     }
  17.     if (a[i] != i) dp[i][1] += c[i];
  18. }
  19.  
  20. void solve() {
  21.     cin >> n;
  22.     a.resize(n);
  23.     c.resize(n);
  24.     adj.resize(n);
  25.     for (int i = 0; i < n; i++) {
  26.         cin >> a[i];
  27.         adj[i].push_back(--a[i]);
  28.     }
  29.     for (auto &i: c) cin >> i;
  30.  
  31.     // find cycles
  32.     vector<bool> v(n);
  33.     cycle.assign(n, true);
  34.     for (int i = 0; i < n; i++) {
  35.         int j = i;
  36.         while (!v[j]) {
  37.             v[j] = true;
  38.             j = a[j];
  39.         }
  40.         for (int k = i; k != j; k = a[k]) {
  41.             cycle[k] = false;
  42.         }
  43.     }
  44.  
  45.     radj.resize(n);
  46.     for (int i = 0; i < n; i++) {
  47.         if (!cycle[i]) {
  48.             radj[a[i]].push_back(i);
  49.         }
  50.     }
  51.  
  52.     // dp
  53.     dp.resize(n);
  54.     for (int i = 0; i < n; i++) {
  55.         if (cycle[i]) calcdp(i);
  56.     }
  57.  
  58.     // dp but for cycles
  59.     ll ans = 0;
  60.     vector<bool> v2(n);
  61.     for (int i = 0; i < n; i++) {
  62.         if (!cycle[i]) continue;
  63.         if (a[i] == i) {
  64.             ans += dp[i][1];
  65.             continue;
  66.         }
  67.         if (v2[i]) continue;
  68.  
  69.         vector<int> cyc;
  70.         for (int j = i; !v2[j]; j = a[j]) {
  71.             v2[j] = true;
  72.             cyc.push_back(j);
  73.         }
  74.         int m = cyc.size();
  75.  
  76.         // i is 0
  77.         array<ll, 2> curdp, prevdp;
  78.         prevdp = {dp[i][0], dp[i][1]};
  79.         for (int k: cyc) {
  80.             if (k == i) continue;
  81.             curdp[0] = prevdp[1] + dp[k][0];
  82.             curdp[1] = min(prevdp[0], prevdp[1]) + dp[k][1];
  83.             swap(curdp, prevdp);
  84.         }
  85.         ll cur0 = prevdp[1];
  86.  
  87.         // i is 1
  88.         prevdp = {(ll)1e18, dp[i][1]};
  89.         for (int k: cyc) {
  90.             if (k == i) continue;
  91.             curdp[0] = prevdp[1] + dp[k][0];
  92.             curdp[1] = min(prevdp[0], prevdp[1]) + dp[k][1];
  93.             swap(curdp, prevdp);
  94.         }
  95.         ll cur1 = min(prevdp[0], prevdp[1]);
  96.         ans += min(cur0, cur1);
  97.     }
  98.  
  99.     // ans
  100.     cout << ans << '\n';
  101. }
  102.  
  103. signed main() {
  104.     cin.tie(0)->sync_with_stdio(0);
  105.     solve();
  106. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/iyNjM2
language:
C++14 (clang 8.0)
created:
337 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!