Submission #1447309

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> ch1[2][110000];
int par1[2][110000];
int root[2];

int rep[2][110000];

//int par2[2][110000];
//vector<int> ch2[2][110000];

vector<int> edges[110000];

int m2[110000];
int vis[110000];

/*void fixtree(int z, int a){
	for(int j = 0; j < ch1[z][a].size(); j++){
		if(m2[a] == 1) par2[z][ch1[z][a][j]] = a;
		if(m2[a] == 0) par2[z][ch1[z][a][j]] = par2[z][a];
		fixtree(z, ch1[z][a][j]);
	}
}*/

void findrep(int z, int a){
	for(int j = 0; j < ch1[z][a].size(); j++){
		findrep(z, ch1[z][a][j]);
	}
	if(m2[a] == 1){
		rep[z][a] = a;
	} else {
		int f = ch1[z][a][ch1[z][a].size()-1];
		rep[z][a] = rep[z][f];
	}
}

void dfs(int a, int c){
	if(vis[a]) return;
	vis[a] = 1;
	m2[a] = c;
	for(int j = 0; j < edges[a].size(); j++){
		dfs(edges[a][j], -c);
	}
}


int main(){
	int n;
	cin >> n;
	for(int z = 0; z < 2; z++){
		for(int i = 0; i < n; i++){
			vis[i] = 0;
			int p;
			cin >> p;
			if(p >= 1) p--;
			par1[z][i] = p;
			if(p != -1){
				ch1[z][p].push_back(i);
			} else {
				root[z] = i;
			}
		}
	}
	for(int i = 0; i < n; i++){
		if((ch1[0][i].size() % 2) != (ch1[1][i].size() % 2)){
			cout << "IMPOSSIBLE" << endl;
			return 0;
		}
		m2[i] = 1 - (ch1[0][i].size() % 2);
	}

	/*par2[0][root[0]] = par1[0][root[0]];
	par2[1][root[1]] = par1[1][root[1]];
	fixtree(0,root[0]);
	fixtree(1,root[1]);

	for(int z = 0; z < 2; z++){
		for(int i = 0; i < n; i++){
			if(par2[z][i] != -1){
				ch2[z][par2[z][i]].push_back(i);
			} else {
				if(m2[i] != 0) ch2[z][n].push_back(i);
			}
		}
	}*/

	findrep(0,root[0]);
	findrep(1,root[1]);

	for(int z = 0; z < 2; z++){
		for(int i = 0; i <= n; i++){
			if(i < n){
			}
			for(int j = 0; j+1 < ch1[z][i].size(); j += 2){
				int a = ch1[z][i][j];
				int b = ch1[z][i][j+1];
				int r = rep[z][a];
				int s = rep[z][b];
				edges[r].push_back(s);
				edges[s].push_back(r);
				//cout << r << " " << s << endl;
			}
		}
	}

	for(int c = 0; c < n; c++){
		dfs(c, m2[c]);
	}
	cout << "POSSIBLE" << endl;
	for(int i = 0; i < n; i++){
		cout << m2[i] << " ";
	}
	cout << endl;
}

Submission Info

Judge Result