Submission #1518195
Source Code Expand
#include <bits/stdc++.h> #define fi first #define se second #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define rng(a) a.begin(),a.end() #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define pb push_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcount #define uni(x) x.erase(unique(rng(x)),x.end()) #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define df(x) int x = in() #define dame { puts("-1"); return 0;} #define show(x) cout<<#x<<" = "<<x<<endl; #define PQ(T) priority_queue<T,vector<T>,greater<T> > #define bn(x) ((1<<x)-1) #define newline puts("") #define v(T) vector<T> #define vv(T) vector<vector<T>> using namespace std; typedef long long int ll; typedef unsigned uint; typedef unsigned long long ull; typedef pair<int,int> P; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<P> vp; inline int in() { int x; scanf("%d",&x); return x;} inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');} template<typename T>istream& operator>>(istream&i,vector<T>&v) {rep(j,sz(v))i>>v[j];return i;} template<typename T>string join(const vector<T>&v) {stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);} template<typename T>ostream& operator<<(ostream&o,const vector<T>&v) {if(sz(v))o<<join(v);return o;} template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v) {return i>>v.fi>>v.se;} template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v) {return o<<v.fi<<","<<v.se;} const int MX = 200005, INF = 1001001001; const ll LINF = 1e18; const double eps = 1e-10; vi to[MX]; vi t; int ui; vi used, vs; int dfs(int v) { if (used[v] == ui) return v; if (used[v]) return -1; used[v] = ui; rep(i,sz(to[v])) { int u = to[v][i]; int r = dfs(u); if (r == -1) continue; vs.pb(v); if (v == r) return -1; return r; } return -1; } int gfs(int v) { set<int> s; rep(i,sz(to[v])) { int u = to[v][i]; if (t[u]) continue; int r = gfs(u); s.insert(r); } for (int i = 0;; ++i) { if (s.count(i)) continue; return i; } } int main() { int n; scanf("%d",&n); rep(i,n) { int p; scanf("%d",&p); --p; to[p].pb(i); } used = vi(n); ui = 1; rep(i,n) if (!used[i]) { dfs(i); ++ui; if (sz(vs)) break; } t = vi(n); for (int v : vs) t[v] = 1; int m = sz(vs); v(set<int>) s(m); rep(i,m) { int v = vs[i]; for (int u : to[v]) { if (t[u]) continue; s[i].insert(gfs(u)); } } // cerr<<vs<<endl; // rep(i,m) { // for (int x : s[i]) cerr<<x<<endl; // cerr<<"---"<<endl; // } vi c; for (int i = 0; sz(c) < 2; ++i) { if (s[0].count(i)) continue; c.pb(i); } s.pb(s[0]); for (int x0 : c) { int x = x0; rrep(i,m) { int j = 0; for (; j == x || s[i].count(j); ++j); x = j; } if (x == x0) { puts("POSSIBLE"); return 0; } } puts("IMPOSSIBLE"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | snuke |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 3372 Byte |
Status | AC |
Exec Time | 71 ms |
Memory | 38004 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:85:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:88:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&p); ^
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 | 3 ms | 4864 KB |
example1 | AC | 2 ms | 4992 KB |
example2 | AC | 2 ms | 4864 KB |
example3 | AC | 3 ms | 4992 KB |
loop0 | AC | 54 ms | 9728 KB |
loop1 | AC | 53 ms | 9728 KB |
loop10 | AC | 53 ms | 9856 KB |
loop11 | AC | 53 ms | 9728 KB |
loop12 | AC | 53 ms | 9728 KB |
loop13 | AC | 54 ms | 9728 KB |
loop14 | AC | 53 ms | 9728 KB |
loop15 | AC | 54 ms | 9728 KB |
loop16 | AC | 54 ms | 9856 KB |
loop17 | AC | 53 ms | 9728 KB |
loop18 | AC | 53 ms | 9728 KB |
loop19 | AC | 53 ms | 9728 KB |
loop2 | AC | 53 ms | 9856 KB |
loop3 | AC | 53 ms | 9728 KB |
loop4 | AC | 54 ms | 9728 KB |
loop5 | AC | 53 ms | 9728 KB |
loop6 | AC | 54 ms | 9728 KB |
loop7 | AC | 53 ms | 9856 KB |
loop8 | AC | 53 ms | 9856 KB |
loop9 | AC | 53 ms | 9728 KB |
loopex0 | AC | 55 ms | 9728 KB |
loopex1 | AC | 53 ms | 9472 KB |
loopex10 | AC | 53 ms | 9472 KB |
loopex11 | AC | 53 ms | 9344 KB |
loopex12 | AC | 54 ms | 9472 KB |
loopex13 | AC | 53 ms | 9472 KB |
loopex14 | AC | 53 ms | 9472 KB |
loopex15 | AC | 54 ms | 9600 KB |
loopex16 | AC | 55 ms | 9600 KB |
loopex17 | AC | 54 ms | 9600 KB |
loopex18 | AC | 55 ms | 9728 KB |
loopex19 | AC | 53 ms | 9472 KB |
loopex2 | AC | 54 ms | 9472 KB |
loopex20 | AC | 53 ms | 9472 KB |
loopex21 | AC | 54 ms | 9600 KB |
loopex22 | AC | 54 ms | 9600 KB |
loopex23 | AC | 53 ms | 9472 KB |
loopex3 | AC | 53 ms | 9472 KB |
loopex4 | AC | 53 ms | 9600 KB |
loopex5 | AC | 54 ms | 9600 KB |
loopex6 | AC | 53 ms | 9344 KB |
loopex7 | AC | 54 ms | 9600 KB |
loopex8 | AC | 54 ms | 9600 KB |
loopex9 | AC | 55 ms | 9728 KB |
rand0 | AC | 18 ms | 9216 KB |
rand1 | AC | 27 ms | 11392 KB |
rand2 | AC | 8 ms | 8448 KB |
rand3 | AC | 52 ms | 21248 KB |
rand4 | AC | 71 ms | 38004 KB |
rand5 | AC | 31 ms | 11648 KB |
rand6 | AC | 14 ms | 10240 KB |
rand7 | AC | 5 ms | 6144 KB |
rand8 | AC | 44 ms | 21244 KB |
rand9 | AC | 5 ms | 6272 KB |
small0 | AC | 3 ms | 4992 KB |
small1 | AC | 2 ms | 4992 KB |
small2 | AC | 3 ms | 4992 KB |
small3 | AC | 2 ms | 4992 KB |
small4 | AC | 3 ms | 4992 KB |
small5 | AC | 2 ms | 4992 KB |
small6 | AC | 3 ms | 4864 KB |
small7 | AC | 3 ms | 4992 KB |
small8 | AC | 3 ms | 4992 KB |
small9 | AC | 3 ms | 4992 KB |