Submission #1690045
Source Code Expand
#include<bits/stdc++.h> #define N 200009 using namespace std; int n,rt,last,a[N],fa[N],fst[N],nxt[N],tg[N],f[N],g[N],bo[N]; void dfs(int x){ int y; for (y=fst[x]; y; y=nxt[y]) if (!bo[y]) dfs(y); for (y=fst[x]; y; y=nxt[y]) if (!bo[y]) tg[f[y]]=x; for (y=0; tg[y]==x; y++); f[x]=y; for (y++; tg[y]==x; y++); g[x]=y; } int main(){ scanf("%d",&n); int i; for (i=1; i<=n; i++){ scanf("%d",&fa[i]); nxt[i]=fst[fa[i]]; fst[fa[i]]=i; } for (i=1; !bo[i]; i=fa[i]) bo[i]=1; memset(bo,0,sizeof(bo)); for (; !bo[i]; i=fa[i]) bo[i]=1; rt=last=i; for (; bo[i]==1; last=i,i=fa[i]){ dfs(i); bo[i]=2; } for (a[rt]=f[rt],i=rt; fa[i]!=rt; i=fa[i]) a[fa[i]]=(a[i]==f[fa[i]]?g[fa[i]]:f[fa[i]]); if (a[last]!=a[rt]){ puts("POSSIBLE"); return 0; } for (a[rt]=g[rt],i=rt; fa[i]!=rt; i=fa[i]) a[fa[i]]=(a[i]==f[fa[i]]?g[fa[i]]:f[fa[i]]); puts(a[last]==f[rt]?"POSSIBLE":"IMPOSSIBLE"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | lych_cys |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 942 Byte |
Status | AC |
Exec Time | 33 ms |
Memory | 6528 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:16:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:19:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&fa[i]); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 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 | 2 ms | 5120 KB |
example1 | AC | 2 ms | 5120 KB |
example2 | AC | 2 ms | 5120 KB |
example3 | AC | 2 ms | 5120 KB |
loop0 | AC | 25 ms | 6400 KB |
loop1 | AC | 25 ms | 6400 KB |
loop10 | AC | 25 ms | 6400 KB |
loop11 | AC | 24 ms | 6400 KB |
loop12 | AC | 24 ms | 6400 KB |
loop13 | AC | 24 ms | 6400 KB |
loop14 | AC | 24 ms | 6400 KB |
loop15 | AC | 25 ms | 6400 KB |
loop16 | AC | 24 ms | 6400 KB |
loop17 | AC | 24 ms | 6400 KB |
loop18 | AC | 24 ms | 6400 KB |
loop19 | AC | 24 ms | 6400 KB |
loop2 | AC | 25 ms | 6400 KB |
loop3 | AC | 24 ms | 6400 KB |
loop4 | AC | 24 ms | 6400 KB |
loop5 | AC | 24 ms | 6400 KB |
loop6 | AC | 24 ms | 6400 KB |
loop7 | AC | 24 ms | 6400 KB |
loop8 | AC | 24 ms | 6400 KB |
loop9 | AC | 24 ms | 6400 KB |
loopex0 | AC | 25 ms | 6400 KB |
loopex1 | AC | 25 ms | 6400 KB |
loopex10 | AC | 24 ms | 6400 KB |
loopex11 | AC | 24 ms | 6272 KB |
loopex12 | AC | 24 ms | 6400 KB |
loopex13 | AC | 25 ms | 6400 KB |
loopex14 | AC | 24 ms | 6400 KB |
loopex15 | AC | 24 ms | 6400 KB |
loopex16 | AC | 25 ms | 6400 KB |
loopex17 | AC | 25 ms | 6400 KB |
loopex18 | AC | 25 ms | 6400 KB |
loopex19 | AC | 24 ms | 6400 KB |
loopex2 | AC | 24 ms | 6400 KB |
loopex20 | AC | 24 ms | 6400 KB |
loopex21 | AC | 25 ms | 6400 KB |
loopex22 | AC | 25 ms | 6400 KB |
loopex23 | AC | 24 ms | 6400 KB |
loopex3 | AC | 24 ms | 6400 KB |
loopex4 | AC | 24 ms | 6400 KB |
loopex5 | AC | 25 ms | 6400 KB |
loopex6 | AC | 24 ms | 6272 KB |
loopex7 | AC | 25 ms | 6400 KB |
loopex8 | AC | 25 ms | 6400 KB |
loopex9 | AC | 25 ms | 6400 KB |
rand0 | AC | 9 ms | 5504 KB |
rand1 | AC | 13 ms | 5760 KB |
rand2 | AC | 4 ms | 5248 KB |
rand3 | AC | 24 ms | 6272 KB |
rand4 | AC | 33 ms | 6528 KB |
rand5 | AC | 14 ms | 5888 KB |
rand6 | AC | 7 ms | 5376 KB |
rand7 | AC | 3 ms | 5248 KB |
rand8 | AC | 21 ms | 6144 KB |
rand9 | AC | 3 ms | 5248 KB |
small0 | AC | 2 ms | 5120 KB |
small1 | AC | 2 ms | 5120 KB |
small2 | AC | 2 ms | 5120 KB |
small3 | AC | 2 ms | 5120 KB |
small4 | AC | 2 ms | 5120 KB |
small5 | AC | 2 ms | 5120 KB |
small6 | AC | 2 ms | 5120 KB |
small7 | AC | 2 ms | 5120 KB |
small8 | AC | 2 ms | 5120 KB |
small9 | AC | 2 ms | 5120 KB |