Submission #3425279
Source Code Expand
#include <iostream> #include <stdio.h> #include <fstream> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <limits.h> #include <math.h> #include <functional> #include <bitset> #include <iomanip> #define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i)) #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n' #define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> Pii; typedef vector<int> vint; typedef vector<ll> vll; const ll INF = INT_MAX; const ll MOD = 1e9+7; int visit[212345]; int cycle_find(const vector<vint>& G,int v,int c){ if(visit[v]==c){ return v; }else if(visit[v]>=0){ return -1; } visit[v]=c; for(int u:G[v]){ int find=cycle_find(G,u,c); if(find>=0) return find; } return -1; } int a[212345]; void dfs(const vector<vint>& G,int v){ if(visit[v]) return; visit[v]=true; set<int> st; for(int u:G[v]){ dfs(G,u); st.insert(a[u]); } a[v]=0; while(st.count(a[v]++)); a[v]--; } int main(){ int N;cin>>N; vector<vint> g(N); vint p(N); repeat(i,N){ cin >> p[i];p[i]--; g[p[i]].push_back(i); } fill(visit,visit+N,-1); int rcycle=-1; repeat(i,N){ rcycle=cycle_find(g,i,i); if(rcycle>=0)break; } //debug(rcycle); //debug(p[rcycle]); fill(visit,visit+N,false); set<int> st; for(int u:g[p[rcycle]]){ if(u==rcycle)continue; dfs(g,u); st.insert(a[u]); } int first=0; while(st.count(first++)); int second=first; first--; while(st.count(second++)); second--; //debug(first); //debug(second); bool ans = false; visit[p[rcycle]]=true; a[p[rcycle]]=first; repeat(i,N){ dfs(g,i); } ans |= a[p[rcycle]]!=a[rcycle]; //debug(ans); //debugArray(a,N); fill(a,a+N,0); fill(visit,visit+N,false); for(int u:g[p[rcycle]]){ if(u==rcycle)continue; dfs(g,u); } visit[p[rcycle]]=true; a[p[rcycle]]=second; repeat(i,N){ dfs(g,i); } ans |= a[p[rcycle]]!=a[rcycle]; //debug(ans); //debugArray(a,N); cout << (ans? "POSSIBLE":"IMPOSSIBLE") << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | hashiryo |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2515 Byte |
Status | WA |
Exec Time | 150 ms |
Memory | 31232 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 | WA | 105 ms | 9728 KB |
loop1 | WA | 105 ms | 9728 KB |
loop10 | AC | 106 ms | 9856 KB |
loop11 | WA | 105 ms | 9856 KB |
loop12 | WA | 106 ms | 9856 KB |
loop13 | WA | 105 ms | 9856 KB |
loop14 | WA | 108 ms | 9728 KB |
loop15 | WA | 105 ms | 9856 KB |
loop16 | WA | 106 ms | 9856 KB |
loop17 | WA | 105 ms | 9728 KB |
loop18 | AC | 106 ms | 9728 KB |
loop19 | AC | 105 ms | 9728 KB |
loop2 | WA | 108 ms | 9856 KB |
loop3 | WA | 107 ms | 9728 KB |
loop4 | WA | 107 ms | 9856 KB |
loop5 | AC | 106 ms | 9728 KB |
loop6 | WA | 103 ms | 9856 KB |
loop7 | WA | 106 ms | 9856 KB |
loop8 | AC | 106 ms | 9856 KB |
loop9 | AC | 105 ms | 9728 KB |
loopex0 | AC | 104 ms | 9856 KB |
loopex1 | AC | 106 ms | 9728 KB |
loopex10 | AC | 103 ms | 9600 KB |
loopex11 | AC | 105 ms | 9600 KB |
loopex12 | AC | 106 ms | 9600 KB |
loopex13 | AC | 106 ms | 9728 KB |
loopex14 | AC | 106 ms | 9600 KB |
loopex15 | AC | 106 ms | 9728 KB |
loopex16 | AC | 108 ms | 9856 KB |
loopex17 | AC | 108 ms | 9728 KB |
loopex18 | AC | 107 ms | 9984 KB |
loopex19 | AC | 101 ms | 9728 KB |
loopex2 | AC | 105 ms | 9600 KB |
loopex20 | AC | 106 ms | 9600 KB |
loopex21 | AC | 107 ms | 9856 KB |
loopex22 | AC | 109 ms | 9856 KB |
loopex23 | AC | 105 ms | 9600 KB |
loopex3 | AC | 105 ms | 9600 KB |
loopex4 | AC | 105 ms | 9728 KB |
loopex5 | AC | 108 ms | 9856 KB |
loopex6 | AC | 108 ms | 9600 KB |
loopex7 | AC | 107 ms | 9728 KB |
loopex8 | AC | 111 ms | 9728 KB |
loopex9 | AC | 109 ms | 9856 KB |
rand0 | AC | 31 ms | 5120 KB |
rand1 | AC | 48 ms | 7552 KB |
rand2 | AC | 13 ms | 3584 KB |
rand3 | AC | 96 ms | 16256 KB |
rand4 | AC | 150 ms | 31232 KB |
rand5 | AC | 56 ms | 8192 KB |
rand6 | AC | 24 ms | 5376 KB |
rand7 | AC | 6 ms | 1536 KB |
rand8 | AC | 83 ms | 15104 KB |
rand9 | AC | 6 ms | 1536 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 | AC | 1 ms | 256 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 |