Exclusive-OR (UVa Live Archive Asia Wuhan 2009)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=359&page=show_problem&problem=2488

問題

なぞの数値がN個存在し、その数値に関しての情報またはクエリーがQ個与えられるのでそれに答える。
情報は、数値pが直接与えられる物、pとqのxorを取った形で与えられる物がある。この情報に矛盾がある場合はそのことを表示しそのテストケースを終了させなければならない。
クエリーはk個の値のxorを取った物を出力しなければならない。ただし、xorを取った値を知ることができないなら"I don't know."と出力する。
1<=N<=20000
2<=Q<=40000
1<=k<=15
0<=p<2^20

解放

まず問題をグラフに直す。
(p1 xor p2)と(p2 xor p3)を知っていれば(p1 xor p3)の値は(p1 xor p2) xor (p2 xor p3)として知ることができるので、(p1 xor p2)をエッジだと思いグラフを作れば良い。
このままだと各クエリーに関してdfsをしなければならないのでO(NQ)となって間に合わない。ここでUnionFindを拡張した物を使えばO(NA)となる。
UnionFindの拡張版は、rootが何かを知ることだけではなく、rootとのxorも取れるようにしておく。rootとのxorの値を求めるのはrootを求めるのと同時に計算でき、rootとのxorをとれれば(p xor q) = (p xor root) xor (root xor q)とできるので高速にxorを計算できる。後は値の代入もrootに押し付けてしまって、矛盾がないかを毎回チェックすれば良い。