Codeforces Round 764 (Div. 3) G – MinOr Tree を解いた記録

問題の概要

\(n\)頂点\(m\)辺の無向グラフが与えられる.辺\(i\)は頂点\(u_{i}, v_{i}\)を結んでおり,コストは\(w_{i}\)である.
全域木に含まれる辺の重みの bitwise OR を最小化せよ.

問題へのリンク

制約

  • \(3 \leq n \leq 2 \times 10^{5}\)
  • \(n-1 \leq m \leq 2 \times 10^{5}\)
  • \(1 \leq w_{i} \leq 10^{9}\)

解法

上位ビットから順に「使用可能な辺の候補のうち,コストを見たときにそのビットが立っていない辺だけで全域木を組めるか?」を確認します.

  • そのビットが立っていない辺だけで全域木を作れる場合は,そのビットが立っていない辺だけを使用可能な辺の候補に残します.
  • そのビットが立っていない辺だけでは全域木を作れない場合は,そのビットは絶対に使わなければならないので使用可能な辺の候補はいじりません.

実装例

提出コード