Submission #3425306

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

int visit[212345];
int cycle_find(const vector<vint>& G,int v,int c){
  if(visit[v]==c){
    return v;
  }else if(visit[v]>=0){
    return -1;
  }
  visit[v]=c;
  for(int u:G[v]){
    int find=cycle_find(G,u,c);
    if(find>=0) return find;
  }
  return -1;
}
int a[212345];
void dfs(const vector<vint>& G,int v){
  if(visit[v]) return;
  visit[v]=true;
  set<int> st;
  for(int u:G[v]){
    dfs(G,u);
    st.insert(a[u]);
  }
  a[v]=0;
  while(st.count(a[v]++));
  a[v]--;
}

int main(){
  int N;cin>>N;
  vector<vint> g(N);
  vint p(N);
  repeat(i,N){
    cin >> p[i];p[i]--;
    g[p[i]].push_back(i);
  }
  fill(visit,visit+N,-1);
  int rcycle=-1;
  repeat(i,N){
    rcycle=cycle_find(g,i,i);
    if(rcycle>=0)break;
  }
  //debug(rcycle);
  //debug(p[rcycle]);
  fill(visit,visit+N,false);
  set<int> st;
  for(int u:g[p[rcycle]]){
    if(u==rcycle)continue;
    dfs(g,u);
    st.insert(a[u]);
  }
  int first=0;
  while(st.count(first++));
  int second=first;
  first--;
  while(st.count(second++));
  second--;
  //debug(first);
  //debug(second);
  bool ans = false;
  visit[p[rcycle]]=true;
  a[p[rcycle]]=first;
  repeat(i,N){
    dfs(g,i);
  }
  ans |= a[p[rcycle]]!=a[rcycle];
  //debug(ans);
  //debugArray(a,N);
  fill(a,a+N,0);
  fill(visit,visit+N,false);
  for(int u:g[p[rcycle]]){
    if(u==rcycle)continue;
    dfs(g,u);
  }
  visit[p[rcycle]]=true;
  a[p[rcycle]]=second;
  repeat(i,N){
    dfs(g,i);
  }
  ans |= (first==a[rcycle]);
  //debug(ans);
  //debugArray(a,N);
  cout << (ans? "POSSIBLE":"IMPOSSIBLE") << endl;
  return 0;
}

Submission Info

Judge Result