blog.bouzuya.net

2023-03-16 ABC120 を解いた / Corne Chocolate の 2 台目

Corne Chocolate をつくった。 2 台目で 1 台目は 2020-09-12 につくったもの。 2023-02-03 に買い 2023-03-11 で失敗し 2023-03-14 にやり直していたもの。

『プロダクトマネジメント』 https://www.oreilly.co.jp/books/9784873119250/ を読んだ。

ABC120 : AtCoder Beginner Contest 120 の A, B, C, D を解いた。

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

fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(Usize1, Usize1); m],
    };
    let mut ans = vec![0_usize; m + 1];
    ans[m] = 0;
    let mut dsu = Dsu::new(n);
    for (i, (a, b)) in ab.into_iter().enumerate().rev() {
        ans[i] = ans[i + 1];
        if dsu.same(a, b) {
            continue;
        } else {
            let size_a = dsu.size(a);
            let size_b = dsu.size(b);
            dsu.merge(a, b);
            ans[i] += size_a * size_b;
        }
    }
    let all = n * (n - 1) / 2;
    for a in ans.into_iter().skip(1) {
        println!("{}", all - a);
    }
}

// dsu

今日のコミット。