[Arc079F] Namori Grundy

题目大意：

一个有向弱联通环套树。

一个点的sg值等于出边连向点的sg值的mex。

试问是否有办法给每个点分配sg值？

试题分析

题目大意把一些难点跳过了？？！

既然是sg值，那么考虑只有一个环的情况。

也就是说这个环必须由0、1构成，并且相邻两个不同，所以是二分图染色。。

那么显然奇环不行而偶环可以。

发现基环外向树上的那些树我们可以的sg值我们可以直接搞出来，那么我们现在可以获得环上每一个点的sg值的下界，下面就是进行调整了。

当所有点下界相同时，显然就是上面我们说过的情况。

不同我们就分情况讨论：

• \(a_{i-1}<a_{i}\) 不需要调整
• \(a_{i-1}=a_{i}\)调整为+1
• \(a_{i-1}>a_{i}\)依旧不需要调整。

这个过程能否停住是我们判断的标准。

显然若干次以后一定可以停住。

那么不合法的情况显然只有一种：奇环+下界相同。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<algorithm>

//#include<ctime>

//#include<cmath>

//#include<queue>

using namespace std;

#define LL long long

inline int read(){

	int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int INF = 2147483600;

const int MAXN = 400010;

int N; int f[MAXN+1];

bool vis[MAXN+1]; int cir[MAXN+1],sta[MAXN+1];

int topx,top; int Next[MAXN<<1],Node[MAXN<<1],Root[MAXN<<1],cnt;

inline void insert(int u,int v){

	Node[++cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt; return;

} bool flag=false;

inline void Get_Cir(int k){

    if(flag) return ; cir[++topx]=k; vis[k]=true;

    for(LL x=Root[k];x;x=Next[x]){

        LL v=Node[x]; if(flag) return ;

        if(vis[v]){

            for(LL j=topx;j>=1&&cir[j]!=v;j--) sta[++top]=cir[j];

            sta[++top]=v; flag=true; return ;

        } else Get_Cir(v);

    } --topx; vis[k]=0; return ;

}

vector<int> vec[MAXN+1];

inline int Get_slope(int k){

	vec[k].push_back(-1);

	for(int x=Root[k];x;x=Next[x]){

		int v=Node[x]; if(vis[v]) continue;

		vec[k].push_back(Get_slope(v));

	} sort(vec[k].begin(),vec[k].end()); vec[k].push_back(INF);

	for(int i=0;i<vec[k].size();i++){

		if(vec[k][i]+1!=vec[k][i+1]){

			return vec[k][i]+1;

		}

	}

}

int col[MAXN+1];

inline bool state(){

	for(int i=1;i<=top;i++) if(col[i]!=col[1]) return false;

	return true;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	N=read(); int x=N;

	for(int i=1;i<=N;i++) f[i]=read(),insert(f[i],i);

	for(int i=1;i<=N&&!flag;i++) Get_Cir(i); memset(vis,false,sizeof(vis));

	if(!(top&1)){puts("POSSIBLE"); return 0;}

	for(int i=1;i<=top;i++) vis[sta[i]]=1;

	for(int i=1;i<=top;i++) col[i]=Get_slope(sta[i]);

	puts(((top&1)&&state())?"IMPOSSIBLE":"POSSIBLE");

	return 0;

}