daily pastebin goal
85%
SHARE
TWEET

Untitled

a guest Jan 21st, 2018 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:251700000")
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <string>
  7. #include <algorithm>
  8. #include <queue>
  9. #include <cstdio>
  10. #include <fstream>
  11. #include <unordered_map>
  12. #include <map>
  13. #include <iterator>
  14. #include <iomanip>
  15. #include <stack>
  16. #include <math.h>
  17. #include <bitset>
  18. #include <assert.h>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef pair<int, int> pii;
  24. typedef unsigned long long ull;
  25. typedef unsigned int ui;
  26. typedef vector<int> vi;
  27.  
  28. #define TASK "magican"
  29. #define mp make_pair
  30. #define X first
  31. #define Y second
  32. #define all(a) (a).begin(), (a).end()
  33. #define inb push_back
  34. #define y1 lubluAU
  35.  
  36. const ll LINF = 9e18;
  37. const long double eps = 1e-9;
  38. const int INF = 2e9;
  39.  
  40. const int M = 2e5 + 5;
  41.  
  42. int n, a[M], us[M], x, was[M], dp[M][2];
  43. vi pr[M];
  44. pii vv[M];
  45. int an1, an2;
  46.  
  47. void dfs(int v)
  48. {
  49.     us[v] = 1;
  50.     if (us[a[v]] == 1)
  51.     {
  52.         us[v] = 3;
  53.         x = a[v];
  54.         return;
  55.     }
  56.     if (!us[a[v]]) dfs(a[v]);
  57.     if (x)
  58.     {
  59.         us[v] = 3;
  60.         if (x == v) x = 0;
  61.         return;
  62.     }
  63.     us[v] = 2;
  64. }
  65.  
  66. void dffs(int v, int f = 0)
  67. {
  68.     if (!f) an1++;
  69.     else an2++;
  70.     for (int i : pr[v])
  71.         if (us[i] != 3)
  72.             dffs(i, f ^ 1);
  73. }
  74.  
  75. int main()
  76. {
  77. #ifdef _DEBUG
  78.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  79. #else
  80.     //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  81.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  82. #endif
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);
  86.     cin >> n;
  87.     for (int i = 1; i <= n; ++i)
  88.     {
  89.         cin >> a[i];
  90.         pr[a[i]].inb(i);
  91.     }
  92.     for (int i = 1; i <= n; ++i)
  93.         if (!us[i])
  94.             dfs(i);
  95.     for (int i = 1; i <= n; ++i)
  96.         if (us[i] == 3)
  97.         {
  98.             an2 = 0, an1 = 0;
  99.             dffs(i);
  100.             vv[i] = { an1, an2 };
  101.         }
  102.     vi tt;
  103.     for(int i = 1; i <= n; ++i)
  104.         if (us[i] == 3)
  105.         {
  106.             tt.inb(i);
  107.             int j = a[i];
  108.             while (j != i)
  109.             {
  110.                 tt.inb(j);
  111.                 j = a[j];
  112.             }
  113.             break;
  114.         }
  115.     int ans = 0;
  116.     for (int qq = 0; qq < 5; ++qq)
  117.     {
  118.         dp[qq][1] = vv[tt[qq]].X;
  119.         dp[qq][0] = -INF;
  120.         for (int i = qq + 1; i < tt.size(); ++i)
  121.         {
  122.             dp[i][0] = max(dp[i - 1][0] + vv[tt[i]].Y, dp[i - 1][1] + vv[tt[i]].Y);
  123.             dp[i][1] = dp[i - 1][0] + vv[tt[i]].X;
  124.         }
  125.         ans = max(ans, dp[tt.size() - 1][0]);
  126.         tt.inb(tt[qq]);
  127.     }
  128.     cout << ans;
  129. }
RAW Paste Data
Top