Submission #1518949
Source Code Expand
#include <iostream> #include <vector> #include <set> using namespace std; vector<int> G[200000],cycle; int used[200000],a[200000],nxt; bool dfs(int v,int par){ for(int to : G[v]){ if(used[to] == par){ cycle.push_back(v); return true; }else if(used[to] != -1) continue; used[to] = v; if(dfs(to,par)){ cycle.push_back(v); return true; } } return false; } int calc(int v,int ext){ if(a[v] != -1) return a[v]; set<int> st; for(int to : G[v]){ if(to == ext) continue; st.insert(calc(to,-1)); } a[v] = 0; while(st.count(a[v])) a[v]++; if(v == cycle[0]){ nxt = a[v] + 1; while(st.count(a[v])) a[v]++; } return a[v]; } int main(){ int n,p[200000]; cin >> n; for(int i = 0;i < n;i++){ cin >> p[i];p[i]--; G[p[i]].push_back(i); used[i] = -1; a[i] = -1; } for(int i = 0;i < n;i++){ if(used[i] == -1) { used[i] = i; dfs(i,i); } } bool flag = false; for(int i = 0;i < 2;i++){ calc(cycle[0],cycle[cycle.size() - 1]); if(i) a[cycle[0]] = nxt; for(int j = 1;j < cycle.size();j++) calc(cycle[j],-1); int tmp = a[cycle[0]]; a[cycle[0]] = -1; calc(cycle[0],-1); if(tmp == a[cycle[0]]) flag = true; for(int j = 0;j < n;j++) a[j] = -1; } if(flag) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | hoget157 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1358 Byte |
Status | WA |
Exec Time | 123 ms |
Memory | 21496 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 | 3 ms | 4992 KB |
example1 | AC | 3 ms | 4992 KB |
example2 | AC | 3 ms | 4992 KB |
example3 | AC | 3 ms | 4992 KB |
loop0 | AC | 105 ms | 9984 KB |
loop1 | AC | 103 ms | 9984 KB |
loop10 | AC | 105 ms | 10112 KB |
loop11 | AC | 105 ms | 9984 KB |
loop12 | AC | 106 ms | 10112 KB |
loop13 | AC | 106 ms | 10112 KB |
loop14 | AC | 104 ms | 9984 KB |
loop15 | AC | 107 ms | 10112 KB |
loop16 | AC | 106 ms | 10112 KB |
loop17 | AC | 107 ms | 9984 KB |
loop18 | AC | 105 ms | 9984 KB |
loop19 | AC | 105 ms | 9984 KB |
loop2 | AC | 104 ms | 10112 KB |
loop3 | AC | 106 ms | 9984 KB |
loop4 | AC | 105 ms | 10112 KB |
loop5 | AC | 107 ms | 9984 KB |
loop6 | AC | 108 ms | 10112 KB |
loop7 | AC | 107 ms | 10112 KB |
loop8 | AC | 107 ms | 10112 KB |
loop9 | AC | 103 ms | 9984 KB |
loopex0 | WA | 106 ms | 10112 KB |
loopex1 | WA | 105 ms | 9984 KB |
loopex10 | AC | 103 ms | 9984 KB |
loopex11 | AC | 104 ms | 9984 KB |
loopex12 | WA | 104 ms | 9984 KB |
loopex13 | AC | 105 ms | 9984 KB |
loopex14 | AC | 105 ms | 9984 KB |
loopex15 | AC | 104 ms | 10112 KB |
loopex16 | AC | 110 ms | 10112 KB |
loopex17 | AC | 104 ms | 9984 KB |
loopex18 | WA | 109 ms | 10240 KB |
loopex19 | AC | 108 ms | 9984 KB |
loopex2 | AC | 106 ms | 9984 KB |
loopex20 | WA | 106 ms | 9984 KB |
loopex21 | AC | 107 ms | 10112 KB |
loopex22 | AC | 103 ms | 10112 KB |
loopex23 | AC | 105 ms | 9984 KB |
loopex3 | AC | 108 ms | 9984 KB |
loopex4 | AC | 109 ms | 9984 KB |
loopex5 | AC | 110 ms | 10112 KB |
loopex6 | AC | 107 ms | 9984 KB |
loopex7 | AC | 110 ms | 10112 KB |
loopex8 | WA | 110 ms | 10112 KB |
loopex9 | AC | 123 ms | 10112 KB |
rand0 | AC | 30 ms | 7296 KB |
rand1 | AC | 45 ms | 8576 KB |
rand2 | AC | 13 ms | 6784 KB |
rand3 | AC | 94 ms | 12800 KB |
rand4 | AC | 122 ms | 21496 KB |
rand5 | AC | 52 ms | 8960 KB |
rand6 | AC | 22 ms | 7680 KB |
rand7 | AC | 8 ms | 5632 KB |
rand8 | AC | 75 ms | 12288 KB |
rand9 | AC | 6 ms | 5632 KB |
small0 | AC | 3 ms | 4992 KB |
small1 | AC | 3 ms | 4992 KB |
small2 | AC | 3 ms | 4992 KB |
small3 | AC | 3 ms | 4992 KB |
small4 | AC | 3 ms | 4992 KB |
small5 | AC | 3 ms | 4992 KB |
small6 | AC | 3 ms | 4992 KB |
small7 | AC | 3 ms | 4992 KB |
small8 | AC | 3 ms | 4992 KB |
small9 | AC | 3 ms | 4992 KB |