Submission #2555788
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define LL long long #define LD long double #define SC(t,x) static_cast<t>(x) #define AR(t) vector < t > #define PII pair < int, int > #define PLL pair < LL, LL > #define PIL pair < int, LL > #define PLI pair < LL, int > #define MP make_pair #define PB push_back #define PF push_front #define POB pop_back #define POF pop_front #define PRF first #define PRS second #define INIT(ar,val) memset ( ar, val, sizeof ( ar ) ) #define lp(loop,start,end) for ( int loop = start; loop < end; ++loop ) #define lpd(loop,start,end) for ( int loop = start; loop > end; --loop ) #define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop ) #define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop ) #define qmax(a,b) (((a)>(b))?(a):(b)) #define qmin(a,b) (((a)<(b))?(a):(b)) #define qabs(a) (((a)>=0)?(a):(-(a))) const int INF = 0x3fffffff; const int SINF = 0x7fffffff; const long long LINF = 0x3fffffffffffffff; const long long SLINF = 0x7fffffffffffffff; const int MAXN = 200007; struct eT { void setd ( int _u, int _v, int _l ) { u = _u, v = _v, last = _l; } int u, v, last; }edge[MAXN]; int n; int ke, la[MAXN]; int p[MAXN]; bool ins[MAXN]; int stk[MAXN], top; int cyc[MAXN], kc; bool inc[MAXN]; int dp[MAXN]; bool hv[MAXN]; void init (); void input (); void work (); int getval ( int now ) { for ( int i = la[now]; ~i; i = edge[i].last ) hv[dp[edge[i].v]] = true; int ans = -1; lp ( i, 0, MAXN ){ if ( !hv[i] ){ ans = i; break; } } for ( int i = la[now]; ~i; i = edge[i].last ) hv[dp[edge[i].v]] = false; return ans; } void dfs ( int now ) { for ( int i = la[now]; ~i; i = edge[i].last ) if ( !inc[edge[i].v] ) dfs ( edge[i].v ); dp[now] = getval ( now ); } int main() { init(); input(); work(); } void init () { // Init Everything Here ios::sync_with_stdio ( false ); } void input () { // input method scanf ( "%d", &n ); lpi ( i, 1, n ) scanf ( "%d", &p[i] ); } void work () { // main work INIT ( la, -1 ); lpi ( i, 1, n ){ edge[ke].setd ( p[i], i, la[p[i]] ); la[p[i]] = ke++; } int now = 1; while ( 1 ){ if ( ins[now] ){ while ( stk[top] ^ now ) cyc[++kc] = stk[--top]; break; } ins[now] = true; stk[top++] = now; now = p[now]; } reverse ( cyc+1, cyc+1+kc ); // lpi ( i, 1, kc ) cerr << cyc[i] << " "; cerr << endl; lpi ( i, 1, kc ) inc[cyc[i]] = true; lpi ( i, 1, kc ) dfs ( cyc[i] ); dp[cyc[kc]] = MAXN-1; int v1 = getval ( cyc[1] ); dp[cyc[1]] = v1; lpi ( i, 2, kc ) dp[cyc[i]] = getval ( cyc[i] ); if ( dp[cyc[1]] ^ dp[cyc[kc]] ){ cout << "POSSIBLE" << endl; return; } dp[cyc[1]] = v1 + 1; lpi ( i, 2, kc ) dp[cyc[i]] = getval ( cyc[i] ); cout << ( ( dp[cyc[1]] == getval ( cyc[1] ) ) ? "POSSIBLE" : "IMPOSSIBLE" ) << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | tqyaaaaang |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2946 Byte |
Status | WA |
Exec Time | 32 ms |
Memory | 6784 KB |
Compile Error
./Main.cpp: In function ‘void input()’: ./Main.cpp:100:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf ( "%d", &n ); ^ ./Main.cpp:101:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] lpi ( i, 1, n ) scanf ( "%d", &p[i] ); ^
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 | 2 ms | 4352 KB |
example1 | AC | 2 ms | 4352 KB |
example2 | AC | 2 ms | 4352 KB |
example3 | AC | 2 ms | 4352 KB |
loop0 | AC | 26 ms | 5760 KB |
loop1 | AC | 26 ms | 5760 KB |
loop10 | AC | 26 ms | 5760 KB |
loop11 | AC | 26 ms | 5760 KB |
loop12 | AC | 26 ms | 5760 KB |
loop13 | AC | 26 ms | 5760 KB |
loop14 | AC | 26 ms | 5760 KB |
loop15 | AC | 26 ms | 5760 KB |
loop16 | AC | 26 ms | 5760 KB |
loop17 | AC | 26 ms | 5760 KB |
loop18 | AC | 28 ms | 5760 KB |
loop19 | AC | 26 ms | 5760 KB |
loop2 | AC | 26 ms | 5760 KB |
loop3 | AC | 26 ms | 5760 KB |
loop4 | AC | 26 ms | 5760 KB |
loop5 | AC | 26 ms | 5760 KB |
loop6 | AC | 26 ms | 5760 KB |
loop7 | AC | 26 ms | 5760 KB |
loop8 | AC | 26 ms | 5760 KB |
loop9 | AC | 26 ms | 5760 KB |
loopex0 | AC | 27 ms | 5760 KB |
loopex1 | AC | 26 ms | 5760 KB |
loopex10 | AC | 26 ms | 5760 KB |
loopex11 | AC | 26 ms | 5760 KB |
loopex12 | AC | 26 ms | 5760 KB |
loopex13 | AC | 26 ms | 5760 KB |
loopex14 | AC | 26 ms | 5760 KB |
loopex15 | WA | 26 ms | 5760 KB |
loopex16 | WA | 26 ms | 5760 KB |
loopex17 | AC | 26 ms | 5760 KB |
loopex18 | WA | 27 ms | 5888 KB |
loopex19 | AC | 26 ms | 5760 KB |
loopex2 | AC | 26 ms | 5760 KB |
loopex20 | WA | 26 ms | 5760 KB |
loopex21 | AC | 27 ms | 5760 KB |
loopex22 | AC | 26 ms | 5760 KB |
loopex23 | AC | 26 ms | 5760 KB |
loopex3 | WA | 26 ms | 5760 KB |
loopex4 | WA | 26 ms | 5760 KB |
loopex5 | AC | 27 ms | 5760 KB |
loopex6 | AC | 26 ms | 5760 KB |
loopex7 | AC | 26 ms | 5760 KB |
loopex8 | WA | 26 ms | 5760 KB |
loopex9 | WA | 27 ms | 5760 KB |
rand0 | WA | 10 ms | 4736 KB |
rand1 | AC | 15 ms | 4992 KB |
rand2 | AC | 5 ms | 4608 KB |
rand3 | AC | 26 ms | 5632 KB |
rand4 | AC | 32 ms | 6784 KB |
rand5 | AC | 16 ms | 4992 KB |
rand6 | AC | 8 ms | 4736 KB |
rand7 | AC | 3 ms | 4480 KB |
rand8 | AC | 23 ms | 5376 KB |
rand9 | AC | 3 ms | 4480 KB |
small0 | AC | 2 ms | 4352 KB |
small1 | AC | 2 ms | 4352 KB |
small2 | AC | 2 ms | 4352 KB |
small3 | AC | 2 ms | 4352 KB |
small4 | AC | 2 ms | 4352 KB |
small5 | AC | 2 ms | 4352 KB |
small6 | AC | 2 ms | 4352 KB |
small7 | AC | 2 ms | 4352 KB |
small8 | AC | 2 ms | 4352 KB |
small9 | AC | 2 ms | 4352 KB |