ABC 401-500/ABC410D - XOR Shortest Walk - 競技プログラミング用 知識集積所【6/15更新】

---

問題

ABC410D

必要知識

B以下レベルの内容は省略

• 隣接リスト（未作成）
• 幅優先探索（未作成）
• 頂点倍加（未作成）

考え方

XORの値は0から1023までの1024通りしかない。
そして頂点は最大1000個。
ということは、頂点番号とXORの値の組で1024000個の頂点を作っても幅優先探索（未作成）による到達可能性確認は十分間に合う。

二次元vector（未作成）でやるなり、頂点ごとにset（未作成）で到達可能なXORの値を管理するなり、実装方法はいろいろある。

解答例

解答例

注意点

別解