Language: C++

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 500000;
int n;
int a[N], used[N], out[N], cycle[N], p[N], mark[N], t, b[N], q[N], k[N];
set < pair < int, int > > s;
vector < int > g[N], G[N], in[N], c[N];
void dfs(int v){
    used[v] = 1;
    for (auto u: g[v]){
        if (u != p[v] && used[u] == 1 && cycle[u] == 0){
            cycle[v] = 1;
            while(v != u){
                v = p[v];
                cycle[v] = 1;

            }
        } else
        if (used[u] == 0){
            p[u] = v;
            dfs(u);
        }
    }
    used[v] = 2;
}
bool check(int v){
    t = -1;
    int res = -1;
    for (auto u: G[v]){
        t = max(t, mark[u]);
        b[mark[u]] = 1;
    }
    for (int i = 0; i <= t + 1; i++){
        if (b[i] == 0 && res == -1){
            res = i;
        }
        b[i] = 0;
    }
    return res;
}
void tr(int V, int x){
    for (auto i: c[V]) if (x == i) return;
    for (int j = 0; j <= n; j++){
        if (!cycle[j]) continue;
        q[j] = 0;
        mark[j] = 0;
    }
    int pr;
    mark[V] = x;
    int v = V;
    for (auto u: in[V]) if (cycle[u]) v = u;
    pr = x;
    int ff = 0;
    while(v != V){
        int y = 0;
        for (auto u: c[v]){
            y = max(y, u);
            b[u] = 1;
        }
        b[pr] = 1;
        y = max(b[pr], y);
        for (int j = 0; j <= y + 1; j++){
            if (b[j] == 0){
                if (q[v] == 1) continue;
                mark[v] = j;
                q[v] = 1;
            }
            b[j] = 0;
        }
        pr = mark[v];
        for (auto u: in[v]) if (cycle[u]) v = u;
    }
    if (pr == mark[V]) return;
    int y = mark[V];
    int z = 1;
    for (auto u: G[v]){
        y = max(mark[u], y);
        b[mark[u]] = 1;
    }
    for (int i = 0; i <= mark[V]; i++){
        if (b[i] == 0 && i < mark[V]) z = 0;
        b[i] = 0;
    }
    if (!z) return;
    cout << "POSSIBLE";
    exit(0);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++){
        int u, v;
        cin >> u;
        v = i;
        g[u].pb(v);
        g[v].pb(u);
        G[u].pb(v);
        in[v].pb(u);
        out[u]++;
    }
    dfs(1);
    for (int i = 1; i <= n; i++) s.insert({out[i], i});
    while(1){
        auto x = *s.begin();
        s.erase(s.begin());
        if (x.F != 0) break;
        if (cycle[x.S]) continue;
        int f = check(x.S);
        mark[x.S] = f;
        for (auto u: in[x.S]){
            s.erase({out[u], u});
            out[u]--;
            s.insert({out[u], u});
        }
    }
    for (int i = 1; i <= n; i++) k[i] = -1;
    for (int i = 1; i <= n; i++)
    if (cycle[i]){
        for (auto u: G[i]){
            if (cycle[u]) continue;
            c[i].pb(mark[u]);
            k[i] = max(k[i], mark[u]);
        }
    }
    for (int i = 1; i <= n; i++)
    if (cycle[i]){
        vector < int > cand;
        for (auto j: c[i]) b[c[j]] = 1;
        for (int j = 0; j <= n + 2; j++){
            if (b[j] == 0) cand.pb(j);
            b[j] = 0;
        }
        tr(i, cand[0]);
        tr(i, cand[1]);
    }
    cout << "IMPOSSIBLE";
}


Compiler output:
a.cc:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main()
      | ^~~~
a.cc: In function 'int main()':
a.cc:143:29: error: no match for 'operator[]' (operand types are 'long long int [500000]' and 'std::vector<long long int>')
  143 |         for (auto j: c[i]) b[c[j]] = 1;
      |                             ^