Submission #1518459

---

Source Code Expand

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

int grn(vector<vector<int>> &e, vector<int> &grundy, int now){
	if(0 <= grundy[now]) return grundy[now];
	vector<int> v;
	for(int next:e[now]) v.emplace_back(grn(e, grundy, next));
	sort(v.begin(), v.end());
	int ret = 0;
	for(int p:v){
		if(p < ret) continue;
		if(ret == p){
			ret++;
			continue;
		}
		break;
	}
	return grundy[now] = ret;
}

bool check(vector<vector<int>> &e, vector<int> &grundy, int i){
	int c = grundy[i];
	set<int> s;
	for(int next:e[i]){
		int t = grundy[next];
		if(t < c) s.insert(t);
		if(t == c) return false;
	}
	return s.size() == c;
}

int main(){
	int n;
	cin >> n;
	vector<int> f(n);
	vector<vector<int>> e(n);
	for(int i = 0; i < n; i++){
		int p;
		cin >> p;
		e[--p].emplace_back(i);
		f[i] = p;
	}
	vector<int> loop, used(n, -1);
	int loop_start = 0;
	{
		int puni = 0;
		while(used[puni] < 0){
			used[puni] = loop.size();
			loop.emplace_back(puni);
			puni = f[puni];
		}
		loop_start = used[puni];
	}
	int min_deg = n + 1, min_vert = 0;
	for(int i = loop_start; i < loop.size(); i++){
		int v = loop[i];
		int deg = e[v].size();
		if(deg < min_deg){
			min_deg = deg;
			min_vert = v;
		}
	}
	vector<int> grundy(n);
	for(int cand = 0; cand <= min_deg; cand++){
		for(int i = 0; i < n; i++){
			grundy[i] = i == min_vert ? cand : -1;
		}
		for(int i = 0; i < n; i++) if(i != min_vert){
			grn(e, grundy, i);
		}
		if(check(e, grundy, min_vert)){
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
}

Submission Info

Judge Result