ARC036 D を解いた - bouzuya.hatenablog.com

偶数メートル (AtCoder Regular Contest 036:D問題) https://atcoder.jp/contests/arc036/tasks/arc036_d
- https://atcoder.jp/contests/arc036/submissions/44170129
- 必要なのは偶奇だけなので距離については偶奇で考えれば良い
- 偶数の距離の道路では合計の偶奇は変わらず、奇数では変わる
- 頂点を偶数と奇数で別頂点として扱い、偶数の距離の道路かどうかでつなぐ頂点を変更する
- あとは Union-Find (Dsu) で偶数頂点間が連結されているかを確認すれば良い

use dsu::*;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        q: usize,
        wxyz: [(usize, Usize1, Usize1, usize); q],
    };

    let mut dsu = Dsu::new(2 * n);
    for (w, x, y, z) in wxyz {
        match w {
            1 => {
                if z % 2 == 0 {
                    dsu.merge(x, y);
                    dsu.merge(x + n, y + n);
                } else {
                    dsu.merge(x, y + n);
                    dsu.merge(x + n, y);
                }
            }
            2 => {
                let ans = dsu.same(x, y);
                println!("{}", if ans { "YES" } else { "NO" });
            }
            _ => unreachable!(),
        }
    }
}

// dsu

今日のコミット。