Submission #1688326
Source Code Expand
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
// _oo0oo_ //
// o8888888o //
// 88" . "88 ------ hzt1 //
// (| -_- |) //
// 0\ = /0 //
// ___/`---'\___ //
// .' \| |// '. //
// / \||| : |||// \ //
// / _||||| -:- |||||- \ //
// | | \ - /// | | //
// | \_| ''\---/'' |_/ | //
// \ .-\__ '-' ___/-. / //
// ___'. .' /--.--\ `. .'___ //
// ."" '< `.___\_<|>_/___.' >' "". //
// | | : `- \`.;`\ _ /`;.`/ - ` : | | //
// \ \ `_. \_ __\ /__ _/ .-` / / //
// =====`-.____`.___ \_____/___.-`___.-'===== //
// `=---=' //
// //
// //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// //
// God-He Bless All. //
// This Code Will Never Explode. //
// //
// //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#include<cassert>
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,Size,stdin);
tail=(head=buffer)+l;
}
if(head==tail) return -1;
return *head++;
}
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;
}
typedef long long ll;
const int maxn=200010;
vector<int>G[maxn];
int n,p[maxn],vis[maxn],A[maxn],B[maxn],in[maxn],first[maxn],nxt[maxn],to[maxn],e;
void AddEdge(int u,int v) {G[v].push_back(u);in[v]++;to[++e]=v;nxt[e]=first[u];first[u]=e;}
int Q[maxn],S[maxn];
int work(int x) {
memset(S,0,sizeof(S));
int y=x;
do {
y=p[y];
if(B[y]>=0) break;
rep(i,0,G[y].size()-1) {
S[B[G[y][i]]]++;
}
rep(i,0,3) if(!S[i]) {B[y]=i;break;}
rep(i,0,3) S[i]=0;
assert(B[y]>=0);
}while(y!=x);
rep(x,1,n) {
rep(i,0,G[x].size()-1) S[B[G[x][i]]]++;
rep(i,0,3) if(!S[i]) {if(i!=B[x]) return 0;break;}
rep(i,0,3) S[i]=0;
}
// rep(i,1,n) printf("%d%c",B[i],i==n?'\n':' ');
return 1;
}
int solve() {
memset(A,-1,sizeof(A));
int l=1,r=0;
rep(i,1,n) if(!in[i]) Q[++r]=i,A[i]=0;
while(l<=r) {
int x=Q[l++];vis[x]=1;
for(int i=first[x];i;i=nxt[i]) if(!(--in[to[i]])) Q[++r]=to[i],A[to[i]]=A[x]^1;
}
rep(i,1,n) if(!vis[i]) {
rep(j,1,n) B[j]=A[j];
B[i]=0;if(work(i)) return 1;
rep(j,1,n) B[j]=A[j];
B[i]=1;if(work(i)) return 1;
rep(j,1,n) B[j]=A[j];
B[i]=2;if(work(i)) return 1;
rep(j,1,n) B[j]=A[j];
B[i]=3;if(work(i)) return 1;
return 0;
}
}
int main() {
n=read();
rep(i,1,n) AddEdge(i,p[i]=read());
puts(solve()?"POSSIBLE":"IMPOSSIBLE");
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Namori Grundy |
User |
wzj52501 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3844 Byte |
Status |
WA |
Exec Time |
51 ms |
Memory |
17408 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2, example3 |
All |
example0, example1, example2, example3, loop0, loop1, loop10, loop11, loop12, loop13, loop14, loop15, loop16, loop17, loop18, loop19, loop2, loop3, loop4, loop5, loop6, loop7, loop8, loop9, loopex0, loopex1, loopex10, loopex11, loopex12, loopex13, loopex14, loopex15, loopex16, loopex17, loopex18, loopex19, loopex2, loopex20, loopex21, loopex22, loopex23, loopex3, loopex4, loopex5, loopex6, loopex7, loopex8, loopex9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, small0, small1, small2, small3, small4, small5, small6, small7, small8, small9 |
Case Name |
Status |
Exec Time |
Memory |
example0 |
AC |
5 ms |
11520 KB |
example1 |
AC |
5 ms |
11520 KB |
example2 |
AC |
5 ms |
11520 KB |
example3 |
AC |
5 ms |
11520 KB |
loop0 |
AC |
32 ms |
15616 KB |
loop1 |
AC |
33 ms |
15616 KB |
loop10 |
AC |
34 ms |
15616 KB |
loop11 |
AC |
34 ms |
15616 KB |
loop12 |
AC |
36 ms |
15616 KB |
loop13 |
AC |
35 ms |
15616 KB |
loop14 |
AC |
35 ms |
15616 KB |
loop15 |
AC |
37 ms |
15616 KB |
loop16 |
AC |
36 ms |
15616 KB |
loop17 |
AC |
35 ms |
15616 KB |
loop18 |
WA |
35 ms |
15616 KB |
loop19 |
WA |
32 ms |
15616 KB |
loop2 |
AC |
32 ms |
15616 KB |
loop3 |
AC |
34 ms |
15616 KB |
loop4 |
AC |
32 ms |
15616 KB |
loop5 |
AC |
33 ms |
15616 KB |
loop6 |
AC |
37 ms |
15616 KB |
loop7 |
AC |
34 ms |
15616 KB |
loop8 |
WA |
33 ms |
15616 KB |
loop9 |
WA |
33 ms |
15616 KB |
loopex0 |
WA |
33 ms |
15616 KB |
loopex1 |
WA |
37 ms |
15616 KB |
loopex10 |
WA |
32 ms |
15616 KB |
loopex11 |
AC |
33 ms |
15616 KB |
loopex12 |
WA |
32 ms |
15616 KB |
loopex13 |
WA |
32 ms |
15616 KB |
loopex14 |
WA |
32 ms |
15616 KB |
loopex15 |
WA |
35 ms |
15616 KB |
loopex16 |
WA |
34 ms |
15616 KB |
loopex17 |
WA |
32 ms |
15616 KB |
loopex18 |
WA |
35 ms |
15744 KB |
loopex19 |
WA |
32 ms |
15616 KB |
loopex2 |
WA |
32 ms |
15616 KB |
loopex20 |
WA |
33 ms |
15616 KB |
loopex21 |
WA |
34 ms |
15616 KB |
loopex22 |
WA |
33 ms |
15616 KB |
loopex23 |
WA |
32 ms |
15616 KB |
loopex3 |
WA |
32 ms |
15616 KB |
loopex4 |
WA |
32 ms |
15616 KB |
loopex5 |
WA |
33 ms |
15616 KB |
loopex6 |
WA |
33 ms |
15616 KB |
loopex7 |
WA |
32 ms |
15616 KB |
loopex8 |
WA |
32 ms |
15616 KB |
loopex9 |
WA |
33 ms |
15616 KB |
rand0 |
WA |
14 ms |
12800 KB |
rand1 |
WA |
18 ms |
13440 KB |
rand2 |
AC |
7 ms |
12160 KB |
rand3 |
WA |
34 ms |
15104 KB |
rand4 |
WA |
51 ms |
17408 KB |
rand5 |
WA |
21 ms |
13696 KB |
rand6 |
WA |
12 ms |
12544 KB |
rand7 |
WA |
7 ms |
11776 KB |
rand8 |
WA |
31 ms |
14720 KB |
rand9 |
WA |
6 ms |
11776 KB |
small0 |
AC |
5 ms |
11520 KB |
small1 |
AC |
5 ms |
11520 KB |
small2 |
AC |
5 ms |
11520 KB |
small3 |
AC |
5 ms |
11520 KB |
small4 |
WA |
5 ms |
11520 KB |
small5 |
AC |
5 ms |
11520 KB |
small6 |
AC |
5 ms |
11520 KB |
small7 |
AC |
5 ms |
11520 KB |
small8 |
AC |
5 ms |
11520 KB |
small9 |
AC |
5 ms |
11520 KB |