kmjp's blog

競技プログラミング参加記です

TopCoder SRM 618 Div1 Easy Family

SRM618は不参加。
練習ではEasy解くの遅かったしMedium時間内に解けなかったし、結果的には出なくてよかった回。
http://community.topcoder.com/stat?c=problem_statement&pm=10541

問題

N人の人がいる。
各人、N人中に親は一人もいないか2人親がいるかどちらかである。
当然ながら2人の親は片方は男性で片方は女性でなければならない。

親子関係が与えられたとき、性別を考慮するとそれらの親子関係は成り立つかどうかを答えよ。

解法

各人の親子関係から、夫婦関係がわかる。
夫婦同士は片方が男性で片方が女性でなければならないので、未処理の人に対して性別を仮置きし、DFSで夫婦関係の人に反対の性別を割り当てていけばよい。
性別で矛盾が出る場合、その親子関係は成り立たない。

class Family {
	public:
	int N;
	int mat[101][101];
	int col[101];
	
	int check(int cur,int c) {
		int i,tot=1;
		col[cur]=c;
		
		FOR(i,N) if(mat[cur][i]) {
			if(col[i]==c) return 0;
			if(col[i]==0) tot &= check(i,3-c);
		}
		return tot;
	}
	
	string isFamily(vector <int> parent1, vector <int> parent2) {
		int i,x;
		N=parent1.size();
		
		ZERO(mat);
		ZERO(col);
		FOR(i,N) if(parent1[i]!=-1) mat[parent1[i]][parent2[i]]=mat[parent2[i]][parent1[i]]=1;
		
		FOR(i,N) if(col[i]==0 && check(i,1)==0) return "Impossible";
		return "Possible";
	}
};

まとめ

練習ではUnion-findや二部マッチングとかが頭に浮かんでしまい、かなり時間を食ってしまった。