Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:251700000")
- #include <iostream>
- #include <vector>
- #include <set>
- #include <string>
- #include <algorithm>
- #include <queue>
- #include <cstdio>
- #include <fstream>
- #include <unordered_map>
- #include <map>
- #include <iterator>
- #include <iomanip>
- #include <stack>
- #include <math.h>
- #include <bitset>
- #include <assert.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef unsigned long long ull;
- typedef unsigned int ui;
- typedef vector<int> vi;
- #define TASK "magican"
- #define mp make_pair
- #define X first
- #define Y second
- #define all(a) (a).begin(), (a).end()
- #define inb push_back
- #define y1 lubluAU
- const ll LINF = 9e18;
- const long double eps = 1e-9;
- const int INF = 2e9;
- const int M = 2e5 + 5;
- int n, a[M], us[M], x, was[M], dp[M][2];
- vi pr[M];
- pii vv[M];
- int an1, an2;
- void dfs(int v)
- {
- us[v] = 1;
- if (us[a[v]] == 1)
- {
- us[v] = 3;
- x = a[v];
- return;
- }
- if (!us[a[v]]) dfs(a[v]);
- if (x)
- {
- us[v] = 3;
- if (x == v) x = 0;
- return;
- }
- us[v] = 2;
- }
- void dffs(int v, int f = 0)
- {
- if (!f) an1++;
- else an2++;
- for (int i : pr[v])
- if (us[i] != 3)
- dffs(i, f ^ 1);
- }
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #else
- //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n;
- for (int i = 1; i <= n; ++i)
- {
- cin >> a[i];
- pr[a[i]].inb(i);
- }
- for (int i = 1; i <= n; ++i)
- if (!us[i])
- dfs(i);
- for (int i = 1; i <= n; ++i)
- if (us[i] == 3)
- {
- an2 = 0, an1 = 0;
- dffs(i);
- vv[i] = { an1, an2 };
- }
- vi tt;
- for(int i = 1; i <= n; ++i)
- if (us[i] == 3)
- {
- tt.inb(i);
- int j = a[i];
- while (j != i)
- {
- tt.inb(j);
- j = a[j];
- }
- break;
- }
- int ans = 0;
- for (int qq = 0; qq < 5; ++qq)
- {
- dp[qq][1] = vv[tt[qq]].X;
- dp[qq][0] = -INF;
- for (int i = qq + 1; i < tt.size(); ++i)
- {
- dp[i][0] = max(dp[i - 1][0] + vv[tt[i]].Y, dp[i - 1][1] + vv[tt[i]].Y);
- dp[i][1] = dp[i - 1][0] + vv[tt[i]].X;
- }
- ans = max(ans, dp[tt.size() - 1][0]);
- tt.inb(tt[qq]);
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement