blog.bouzuya.net

2023-07-29 ABC312 に参加した / ABC065 D を解いた

ABC312 に参加した。 1299 → 1312 (+13) 。 https://atcoder.jp/users/bouzuya/history/share/abc312 。 A, B, C, D の 4 完。 E はヤバそうだったのでほとんど考察なしにスキップ。 F はおおまかな考察は正しいもののうまく実装できず終了。

『シン・仮面ライダー』を観た。血が多い。

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

fn main() {
    input! {
        n: usize,
        k: usize,
        l: usize,
        pq: [(Usize1, Usize1); k],
        rs: [(Usize1, Usize1); l],
    };

    let mut dsu1 = Dsu::new(n);
    for (p, q) in pq {
        dsu1.merge(p, q);
    }

    let mut dsu2 = Dsu::new(n);
    for (r, s) in rs {
        dsu2.merge(r, s);
    }

    let mut map = HashMap::new();
    for i in 0..n {
        let key = (dsu1.leader(i), dsu2.leader(i));
        *map.entry(key).or_insert(0) += 1;
    }

    let ans = (0..n)
        .map(|i| (dsu1.leader(i), dsu2.leader(i)))
        .map(|key| map[&key])
        .collect::<Vec<usize>>();
    let mut s = String::new();
    for (i, a_i) in ans.iter().copied().enumerate() {
        s.push_str(&format!(
            "{}{}",
            a_i,
            if i == ans.len() - 1 { '\n' } else { ' ' }
        ));
    }
    print!("{}", s);
}

// dsu

今日のコミット。