fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll n,a[100005],kq[100005],d[100005],t = 0,x = 0,kt;
  5. vector <int> ve;
  6. int main()
  7. {
  8.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9.     //freopen("TREAT.inp", "r", stdin);
  10.     //freopen("TREAT.out", "w", stdout);
  11.     cin >> n;
  12.     for(int i = 1; i <= n; i++)
  13.     {
  14.         cin >> a[i];
  15.         kq[i] = 0;
  16.         if(a[i] == i)
  17.             kq[i] = 1;
  18.         d[i] = 0;
  19.     }
  20.     for(int i = 1; i <= n; i++)
  21.     {
  22.         if(!kq[i])
  23.         {
  24.             ll j = i;
  25.             ve.push_back(i);
  26.             d[i]++;
  27.             t = 1;
  28.             x = 0;
  29.             kt = 0;
  30.             while(d[j] <= 1)
  31.             {
  32.                 j = a[j];
  33.                 ve.push_back(j);
  34.                 d[j]++;
  35.                 if(kq[j] != 0)
  36.                 {
  37.                     x = 1;
  38.                     t += kq[j];
  39.                     break;
  40.                 }
  41.                 if(d[j] <= 1)
  42.                     t++;
  43.                 else kt = j;
  44.             }
  45.             ll y = 0,tam = 0;
  46.             for(auto k : ve)
  47.             {
  48.                     if(k == kt && y == 0)
  49.                     {
  50.                         y = 1;
  51.                         kq[k]= t - tam;
  52.                     }
  53.                     else if(y == 1)
  54.                     {
  55.                         kq[k]= t - tam;
  56.                     }
  57.                     else if(k == kt && y == 1)
  58.                     {
  59.                         y = 0;
  60.                         kq[k]= t - tam;
  61.                     }
  62.                     else
  63.                     {
  64.                         kq[k] = t - tam;
  65.                         tam++;
  66.                     }
  67.                 d[k] = 0;
  68.             }
  69.             kq[i] = t;
  70.             ve.clear();
  71.         }
  72.     }
  73.     //cout << '\n';
  74.     for(int i = 1; i <= n; i++)
  75.         cout << kq[i] << '\n';
  76. }
  77.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/r9qUa8
language:
C++14 (gcc 8.3)
created:
86 days 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!