kojingharangの日記

SRM 618 Div1 250 Family

12:30 |

• 親ノードが0個か2個なDAGが与えられる。ノードに男か女ラベルを割り当てたい。親ノードがある場合は必ず男女の組み合わせにできるかどうかを求めよ。
• 1≦ノード数≦100

• 親がいるならそれらのラベルは異なっている必要がある。
• これを、全ノードについて、ノードID→それと異なるべきノードIDという形で覚えておく
• node i に対して異なるべきノードたちは全て同じラベルである必要がある。ラベルが２種類なので。
• 同じであるべきものを union find たんでまとめる
• 再度異なるべきものを見て、それらが同じラベルということになってたら矛盾なので Impossible
• 矛盾してなければ Possible

• accepted

• コードを書き終わってコンパイルしたらコンパイルエラーもなく1回で全テスト通ったのでそのままsubmitした。なかなかない事なのでとても気持ちよかった。(*´～｀*)

class Family {
	public:
	string isFamily(vector <int> P1, vector <int> P2) {
		int N=P1.size();
		VVI diff(N, VI());
		REP(i, N) {
			if(P1[i]==-1) continue;
			diff[P1[i]].PB(P2[i]);
			diff[P2[i]].PB(P1[i]);
		}
		UnionFind uf(N);
		REP(i, N) {
			REP(j, diff[i].size()) {
				uf.Union(diff[i][0], diff[i][j]);
			}
		}
		REP(i, N) {
			REP(j, diff[i].size()) {
				if(uf.Find(i, diff[i][j])) return "Impossible";
			}
		}
		return "Possible";
	}
};

ツイートする