Submission #1518436
Source Code Expand
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; int grn(vector<vector<int>> &e, vector<int> &grundy, int now){ if(0 <= grundy[now]) return grundy[now]; vector<int> v; for(int next:e[now]) v.emplace_back(grn(e, grundy, next)); sort(v.begin(), v.end()); int ret = 0; for(int p:v){ if(p < ret) continue; if(ret == p){ ret++; continue; } break; } return grundy[now] = ret; } bool check(vector<vector<int>> &e, vector<int> &grundy, int i){ int c = grundy[i]; set<int> s; for(int next:e[i]){ int t = grundy[next]; if(t < c) s.insert(t); if(t == c) return false; } return s.size() == c; } int main(){ int n; cin >> n; vector<int> f(n); vector<vector<int>> e(n); for(int i = 0; i < n; i++){ int p; cin >> p; e[--p].emplace_back(i); f[i] = p; } vector<int> loop, used(n, -1); int loop_start = 0; { int puni = 0; while(used[puni] < 0){ used[puni] = loop.size(); loop.emplace_back(puni); puni = f[puni]; } loop_start = puni; } int min_deg = n + 1, min_vert = 0; for(int i = loop_start; i < loop.size(); i++){ int v = loop[i]; int deg = e[v].size(); if(deg < min_deg){ min_deg = deg; min_vert = v; } } vector<int> grundy(n); for(int cand = 0; cand <= min_deg; cand++){ for(int i = 0; i < n; i++){ grundy[i] = i == min_vert ? cand : -1; } for(int i = 0; i < n; i++) if(i != min_vert){ grn(e, grundy, i); } if(check(e, grundy, min_vert)){ cout << "POSSIBLE" << endl; return 0; } } cout << "IMPOSSIBLE" << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | jbyxm |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1640 Byte |
Status | RE |
Exec Time | 762 ms |
Memory | 379392 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 | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
loop0 | RE | 722 ms | 349952 KB |
loop1 | RE | 734 ms | 351744 KB |
loop10 | RE | 670 ms | 337536 KB |
loop11 | RE | 720 ms | 351232 KB |
loop12 | RE | 709 ms | 349056 KB |
loop13 | RE | 680 ms | 336768 KB |
loop14 | RE | 739 ms | 354432 KB |
loop15 | RE | 724 ms | 350592 KB |
loop16 | RE | 678 ms | 340608 KB |
loop17 | RE | 704 ms | 349696 KB |
loop18 | RE | 731 ms | 351232 KB |
loop19 | RE | 699 ms | 344960 KB |
loop2 | RE | 675 ms | 337280 KB |
loop3 | RE | 697 ms | 345472 KB |
loop4 | RE | 692 ms | 344960 KB |
loop5 | RE | 737 ms | 352768 KB |
loop6 | RE | 686 ms | 339840 KB |
loop7 | RE | 675 ms | 338048 KB |
loop8 | RE | 674 ms | 337408 KB |
loop9 | RE | 752 ms | 356224 KB |
loopex0 | RE | 722 ms | 352128 KB |
loopex1 | RE | 761 ms | 365056 KB |
loopex10 | RE | 700 ms | 349056 KB |
loopex11 | RE | 716 ms | 376832 KB |
loopex12 | RE | 762 ms | 364672 KB |
loopex13 | RE | 737 ms | 358400 KB |
loopex14 | RE | 708 ms | 349056 KB |
loopex15 | RE | 688 ms | 342784 KB |
loopex16 | RE | 718 ms | 358656 KB |
loopex17 | RE | 734 ms | 356352 KB |
loopex18 | RE | 710 ms | 346112 KB |
loopex19 | RE | 665 ms | 337024 KB |
loopex2 | RE | 682 ms | 343552 KB |
loopex20 | RE | 718 ms | 352896 KB |
loopex21 | RE | 746 ms | 357248 KB |
loopex22 | RE | 682 ms | 340736 KB |
loopex23 | RE | 707 ms | 347904 KB |
loopex3 | RE | 654 ms | 345088 KB |
loopex4 | RE | 723 ms | 351872 KB |
loopex5 | RE | 736 ms | 358272 KB |
loopex6 | RE | 747 ms | 379392 KB |
loopex7 | RE | 710 ms | 351104 KB |
loopex8 | RE | 706 ms | 358400 KB |
loopex9 | RE | 734 ms | 352384 KB |
rand0 | AC | 26 ms | 4736 KB |
rand1 | AC | 40 ms | 7040 KB |
rand2 | AC | 11 ms | 2560 KB |
rand3 | AC | 79 ms | 15104 KB |
rand4 | AC | 106 ms | 20596 KB |
rand5 | RE | 497 ms | 306816 KB |
rand6 | AC | 23 ms | 4864 KB |
rand7 | AC | 5 ms | 1408 KB |
rand8 | AC | 68 ms | 13948 KB |
rand9 | AC | 5 ms | 1408 KB |
small0 | AC | 1 ms | 256 KB |
small1 | AC | 1 ms | 256 KB |
small2 | AC | 1 ms | 256 KB |
small3 | AC | 1 ms | 256 KB |
small4 | RE | 271 ms | 306048 KB |
small5 | AC | 1 ms | 256 KB |
small6 | AC | 1 ms | 256 KB |
small7 | AC | 1 ms | 256 KB |
small8 | AC | 1 ms | 256 KB |
small9 | AC | 1 ms | 256 KB |