Submission #2555801

---

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;
	dp[cyc[1]] = getval ( cyc[1] );
	lpi ( i, 2, kc ) dp[cyc[i]] = getval ( cyc[i] );
	if ( dp[cyc[1]] == getval ( cyc[1] ) ){
		cout << "POSSIBLE" << endl;
		return;
	}
	dp[cyc[kc]] = dp[cyc[1]];
	dp[cyc[1]] = getval ( cyc[1] );
	lpi ( i, 2, kc ) dp[cyc[i]] = getval ( cyc[i] );
	cout << ( ( dp[cyc[1]] == getval ( cyc[1] ) ) ? "POSSIBLE" : "IMPOSSIBLE" ) << endl;
}

Submission Info

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