Submission #1518903

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<int> G[200000],cycle;
int used[200000],a[200000];

bool dfs(int v,int par){
	for(int to : G[v]){
		if(used[to] == par){
			cycle.push_back(v);
			return true;
		}else if(used[to] != -1) continue;
		used[to] = v;
		if(dfs(to,par)){
			cycle.push_back(v);
			return true;
		}
	}
	return false;
}
int calc(int v,int ext){
	if(a[v] != -1) return a[v];
	set<int> st;
	for(int to : G[v]){
		if(to == ext) continue;
		st.insert(calc(to,-1));
	}
	a[v] = 0;
	while(st.count(a[v])) a[v]++;
	return a[v];
}

int main(){
	int n,p[200000];
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> p[i];p[i]--;
		G[p[i]].push_back(i);
		used[i] = -1;
		a[i] = -1;
	}
	for(int i = 0;i < n;i++){
		if(used[i] == -1) {
			used[i] = i;
			dfs(i,i);
		}
	}
	bool flag = false;
	for(int i = 0;i < 2;i++){
		calc(cycle[0],cycle[cycle.size() - 1]);
		a[cycle[0]] += i;
		for(int j = 1;j < cycle.size();j++) calc(cycle[j],-1);
		int tmp = a[cycle[0]];
		a[cycle[0]] = -1;
		calc(cycle[0],-1);
		if(tmp == a[cycle[0]]) flag = true;
		for(int j = 0;j < n;j++) a[j] = -1;
	}
	if(flag) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
	return 0;
}

Submission Info

Judge Result