blog.bouzuya.net

2023-07-31 ABC040 D を解いた

bouzuya/tsukota のデータを PC からスクリプトで更新できるようにしたい。その準備として models パッケージを追加した。

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

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

    #[derive(Clone, Copy, Debug)]
    enum Query {
        Road { a: usize, b: usize, y: usize },
        Citizen { j: usize, v: usize, w: usize },
    }
    use Query::*;

    let mut queries = vec![];
    for (a, b, y) in aby {
        queries.push(Road { a, b, y });
    }
    for (j, (v, w)) in vw.iter().copied().enumerate() {
        queries.push(Citizen { j, v, w });
    }

    queries.sort_by_key(|q| match q {
        Road { y, .. } => *y,
        Citizen { w, .. } => *w,
    });

    let mut ans = vec![0; q];
    let mut dsu = Dsu::new(n);
    for q in queries.iter().copied().rev() {
        match q {
            Road { a, b, .. } => {
                dsu.merge(a, b);
            }
            Citizen { j, v, .. } => {
                ans[j] = dsu.size(v);
            }
        }
    }

    for a in ans {
        println!("{}", a);
    }
}

// dsu

今日のコミット。