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や二部マッチングとかが頭に浮かんでしまい、かなり時間を食ってしまった。