fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebear"
  33. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  34.  
  35. const int MOD = 1e9 + 7;
  36. const int inf = 1e9 + 27092008;
  37. const ll INF = 1e18 + 27092008;
  38. const int N = 2e5 + 5;
  39. int n, p[N];
  40. int cnt[N];
  41. bool vis[N];
  42. vector<int> lenCycle;
  43. int notCycle;
  44. vector<int> G[N];
  45. int dist[N], dist_to_cycle[N], par[N];
  46.  
  47. struct DisjointSet {
  48.     vector<int> lab;
  49.     DisjointSet(int n = 0): lab(n + 5, -1) {}
  50.  
  51.     int root(int v) {
  52.         return lab[v] < 0 ? v  : lab[v] = root(lab[v]);
  53.     }
  54.  
  55.     bool unite(int u, int v) {
  56.         u = root(u); v = root(v);
  57.         if (u == v) return false;
  58.         if (lab[u] > lab[v]) swap(u, v);
  59.         lab[u] += lab[v];
  60.         lab[v] = u;
  61.         return true;
  62.     }
  63. };
  64.  
  65. int power(int x, int k) {
  66.     int res = 1;
  67.     while(k) {
  68.         if (k & 1) res = 1LL * res * x % MOD;
  69.         k >>= 1;
  70.         x = 1LL * x * x % MOD;
  71.     }
  72.     return res;
  73. }
  74.  
  75. int BFS(int sta, int dest) {
  76.     queue<int> q;
  77.     dist[sta] = 1;
  78.     q.push(sta);
  79.     int mx = 0;
  80.     while(!q.empty()) {
  81.         int u = q.front(); q.pop();
  82.         maximize(mx, dist[u]);
  83.         for(int v : G[u]) if (dist[v] == 0) {
  84.             if (u == sta && v == dest) continue;
  85.             dist[v] = dist[u] + 1;
  86.             par[v] = u;
  87.             q.push(v);
  88.         }
  89.     }
  90.  
  91.     if (sta == dest) {
  92.         maximize(notCycle, mx);
  93.         return 0;
  94.     }
  95.  
  96.     if (par[dest] == 0) {
  97.         dist[dest] = 2;
  98.         par[dest] = sta;
  99.     }
  100.  
  101.     int res = dist[dest];
  102.  
  103.     while(dest != sta) {
  104.         dist_to_cycle[dest] = 1;
  105.         q.push(dest);
  106.         dest = par[dest];
  107.     }
  108.  
  109.     dist_to_cycle[sta] = 1;
  110.     q.push(sta);
  111.  
  112.     while(!q.empty()) {
  113.         int u = q.front(); q.pop();
  114.         for(int v : G[u]) if (dist_to_cycle[v] == 0) {
  115.             dist_to_cycle[v] = dist_to_cycle[u] + 1;
  116.             q.push(v);
  117.         }
  118.     }
  119.  
  120.     return res;
  121. }
  122.  
  123. void init(void) {
  124.     cin >> n;
  125.     FOR(i, 1, n) cin >> p[i];
  126. }
  127.  
  128. void process(void) {
  129.     vector<int> sta, dest;
  130.     DisjointSet dsu(n);
  131.     FOR(i, 1, n) {
  132.         G[i].pb(p[i]);
  133.         G[p[i]].pb(i);
  134.         if (dsu.unite(i, p[i]) == false) {
  135.             sta.pb(i);
  136.             dest.pb(p[i]);
  137.         }
  138.     }
  139.  
  140.     FOR(i, 0, (int)sta.size() - 1) lenCycle.pb(BFS(sta[i], dest[i]));
  141.  
  142.     int ans = 1;
  143.     for(int x : lenCycle) {
  144.         for(int j = 2; j * j <= x; j++) {
  145.             int res = 0;
  146.             while(x % j == 0) {
  147.                 res++;
  148.                 x /= j;
  149.             }
  150.             maximize(cnt[j], res);
  151.         }
  152.         if (x > 1) maximize(cnt[x], 1);
  153.     }
  154.  
  155.     FOR(i, 1, 100000) ans = 1LL * ans * power(i, cnt[i]) % MOD;
  156.     cout << max((ans + *max_element(dist_to_cycle + 1, dist_to_cycle + n + 1) - 1) % MOD, notCycle);
  157. }
  158.  
  159. int main() {
  160.     ios_base::sync_with_stdio(0);
  161.     cin.tie(0); cout.tie(0);
  162.     if (fopen(task".inp", "r")) {
  163.         freopen(task".inp", "r", stdin);
  164.         freopen(task".out", "w", stdout);
  165.     }
  166.     int tc = 1;
  167. //    cin >> tc;
  168.     while(tc--) {
  169.         init();
  170.         process();
  171.     }
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0.01s 9708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QRVOGF
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

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!