Submission #1882251
Source Code Expand
#include <cstdio> #include <vector> #include <algorithm> int p[200001], N, d[200001], q[200001], D, vi[200001], sg[200001], cir[200001], L, w1[200001], w2[200001], w[200001]; std::vector < int > E[200001]; bool NiroBC(int start) { w[1] = start; for (int i = 2; i <= L; i++) w[i] = w[i - 1] == w1[i] ? w2[i] : w1[i]; return w[1] == (w[L] == w1[1] ? w2[1] : w1[1]); } int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", p + i); E[p[i]].push_back(i); d[p[i]]++; } for (int i = 1; i <= N; i++) if (!d[i]) q[++D] = i; while (D) { int u = q[D--]; for (int v : E[u]) vi[sg[v]] = 1; while (vi[sg[u]]) sg[u]++; for (int v : E[u]) vi[sg[v]] = 0; if (!--d[p[u]]) q[++D] = p[u]; } for (int i = std::find(d + 1, d + N + 1, 1) - d; d[i] == 1; i = p[i]) d[cir[++L] = i] = -1; for (int i = 1; i <= L; i++) { int u = cir[i]; for (int v : E[u]) if (d[v] != -1) vi[sg[v]] = 1; while (vi[w1[i]]) w1[i]++; w2[i] = w1[i] + 1; while (vi[w2[i]]) w2[i]++; for (int v : E[u]) if (d[v] != -1) vi[sg[v]] = 0; } puts(NiroBC(w1[1]) || NiroBC(w2[1]) ? "POSSIBLE" : "IMPOSSIBLE"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | NiroBC |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1224 Byte |
Status | AC |
Exec Time | 52 ms |
Memory | 17152 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:15:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^ ./Main.cpp:18:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", p + 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 | 4 ms | 10496 KB |
example1 | AC | 4 ms | 10496 KB |
example2 | AC | 4 ms | 10496 KB |
example3 | AC | 4 ms | 10496 KB |
loop0 | AC | 50 ms | 14720 KB |
loop1 | AC | 47 ms | 14720 KB |
loop10 | AC | 47 ms | 14720 KB |
loop11 | AC | 47 ms | 14720 KB |
loop12 | AC | 47 ms | 14720 KB |
loop13 | AC | 47 ms | 14720 KB |
loop14 | AC | 47 ms | 14720 KB |
loop15 | AC | 47 ms | 14720 KB |
loop16 | AC | 47 ms | 14720 KB |
loop17 | AC | 47 ms | 14720 KB |
loop18 | AC | 47 ms | 14720 KB |
loop19 | AC | 47 ms | 14720 KB |
loop2 | AC | 47 ms | 14720 KB |
loop3 | AC | 47 ms | 14720 KB |
loop4 | AC | 47 ms | 14720 KB |
loop5 | AC | 49 ms | 14720 KB |
loop6 | AC | 47 ms | 14720 KB |
loop7 | AC | 47 ms | 14720 KB |
loop8 | AC | 51 ms | 14720 KB |
loop9 | AC | 47 ms | 14720 KB |
loopex0 | AC | 48 ms | 14848 KB |
loopex1 | AC | 47 ms | 14720 KB |
loopex10 | AC | 47 ms | 14720 KB |
loopex11 | AC | 48 ms | 14720 KB |
loopex12 | AC | 47 ms | 14720 KB |
loopex13 | AC | 48 ms | 14720 KB |
loopex14 | AC | 47 ms | 14720 KB |
loopex15 | AC | 50 ms | 14720 KB |
loopex16 | AC | 50 ms | 14848 KB |
loopex17 | AC | 48 ms | 14720 KB |
loopex18 | AC | 50 ms | 14848 KB |
loopex19 | AC | 48 ms | 14720 KB |
loopex2 | AC | 47 ms | 14720 KB |
loopex20 | AC | 50 ms | 14720 KB |
loopex21 | AC | 48 ms | 14848 KB |
loopex22 | AC | 48 ms | 14848 KB |
loopex23 | AC | 47 ms | 14720 KB |
loopex3 | AC | 47 ms | 14720 KB |
loopex4 | AC | 48 ms | 14720 KB |
loopex5 | AC | 48 ms | 14848 KB |
loopex6 | AC | 47 ms | 14720 KB |
loopex7 | AC | 48 ms | 14720 KB |
loopex8 | AC | 48 ms | 14720 KB |
loopex9 | AC | 48 ms | 14848 KB |
rand0 | AC | 16 ms | 11648 KB |
rand1 | AC | 23 ms | 12416 KB |
rand2 | AC | 8 ms | 11136 KB |
rand3 | AC | 42 ms | 14464 KB |
rand4 | AC | 52 ms | 17152 KB |
rand5 | AC | 26 ms | 12672 KB |
rand6 | AC | 12 ms | 11520 KB |
rand7 | AC | 6 ms | 10752 KB |
rand8 | AC | 35 ms | 13952 KB |
rand9 | AC | 6 ms | 10752 KB |
small0 | AC | 4 ms | 10496 KB |
small1 | AC | 4 ms | 10496 KB |
small2 | AC | 4 ms | 10496 KB |
small3 | AC | 5 ms | 10496 KB |
small4 | AC | 4 ms | 10496 KB |
small5 | AC | 4 ms | 10496 KB |
small6 | AC | 4 ms | 10496 KB |
small7 | AC | 4 ms | 10496 KB |
small8 | AC | 4 ms | 10496 KB |
small9 | AC | 4 ms | 10496 KB |