SRM 658 Div2Hard : OddEvenTreeHard

問題

http://lealgorithm.blogspot.jp/2015/05/srm-658-div1-easy-oddeventree.html
と同じだけど、x[i][j]='?'というのが許されている。(?だとOddとEvenどちらでも良い)

解法

Div1の方とほぼ同じ。
まず対称性の確認とかx[i][i]=='O'だったらはじくとかやって、ワーシャルフロイドでx[i][j]+x[j][k]の偶奇とx[i][k]の偶奇の確認(もしx[i][k]が?だったら埋める)というのをやり、
それでもどこかに?があった場合はまずそれをOにしてみて矛盾する箇所がないか確認して、もし矛盾したらEにする、というのを行うとxから?がなくなるので後はDiv1と同じ構成方法を用いて構成する。

ソースコード

https://gist.github.com/knewknowl/2b26f73992fb90439370