AtCoder Regular Contest 036：D - 偶数メートル

問題

https://atcoder.jp/contests/arc036/tasks/arc036_d

考え方

考えていたこと

偶数メートルで到達できればよいので、各辺の長さ z_i については偶奇のみが重要そう。しかし偶数長の辺どおしでの UnionFind、奇数長の辺どおしでの UnionFind を考えてもうまくいかない...

解説

偶数長の集合、奇数長の集合で各頂点をみたときに、辺で頂点を連結されるとき

(1)：辺の長さが偶数の場合

偶数長どおしで連結される

(2)：辺の長さが奇数の場合

偶数長の頂点と奇数長の頂点で連結される

よって、偶数長の頂点と奇数長の頂点をそれぞれ保持しておいて、辺の長さに応じて上記の操作をすることで連結性を判定できる。解は偶数長の頂点集合として考えたときに x, y が連結であれば、YES そうでなければ NO となる。

Submission #4048526 - AtCoder Regular Contest 036

得た知見(典型ポイント)

  • 頂点を倍化してなんやかんやする
  • 偶奇の性質(偶数に偶数を足しても偶数、偶数に奇数を足すと奇数)

類題