Submission #1549476

---

Source Code Expand

#include <bits/stdc++.h>
#define N 200005
 
using namespace std;
typedef pair <int,int> P;
 
vector <int> vec[N];
int par[N],dep[N];
int pr[N],ng[N];
bool use[N];
int n;
 
int rev(int v)
{
	if(v>=n) return v-n;
	return v+n;
}
int dfs(int v,int d)
{
	dep[v]=d;
	int a=-1;
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		int tg=dfs(to,d+1);
		if(tg!=-1)
		{
			if(a==-1) a=tg;
			else
			{
				//printf("%d %d\n",a,tg);
				pr[a]=tg;
				pr[tg]=a;
				a=-1;
			}
		}
	}
	if(a==-1) a=v;
	return a;
}
int LCA(int a,int b)
{
	while(a!=b)
	{
		if(dep[a]>dep[b]) swap(a,b);
		b=par[b];
	}
	return a;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<2*n;i++)
	{
		int p;
		scanf("%d",&p);p--;
		if(p<0) p=2*n;
		else if(i>=n) p+=n;
		par[i]=p;
		vec[p].push_back(i);
	}
	for(int i=0;i<n;i++)
	{
		if(vec[i].size()%2!=vec[i+n].size()%2)
		{
			puts("IMPOSSIBLE");
			return 0;
		}
	}
	memset(pr,-1,sizeof(pr));
	dfs(2*n,0);
	for(int i=0;i<2*n;i++)
	{
		if(!use[i]&&pr[i]!=-1)
		{
			use[i]=true;
			int now=i;
			do
			{
				use[now]=true;
				int to=pr[now];
				int p=LCA(now,to);
				//if(now==i) printf("%d %d : %d %d\n",now,to,p,i);
				for(int j=now;j!=p;j=par[j]) ng[j]=1;
				for(int j=to;j!=p;j=par[j]) ng[j]=-1;
				now=rev(to);
			}while(now!=i);
		}
	}
	puts("POSSIBLE");
	for(int i=0;i<n;i++)
	{
		int ret=ng[i];
		for(int j=0;j<vec[i].size();j++)
		{
			int to=vec[i][j];
			ret-=ng[to];
		}
		if(i!=0) printf(" ");
		printf("%d",ret);
	}puts("");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:56:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);p--;
                 ^

Judge Result