結果

問題 No.2912 ０次パーシステントホモロジー
ユーザー Yukino DX.Yukino DX.
提出日時 2024-11-06 14:40:32
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 187 ms / 2,000 ms
コード長 2,585 bytes
コンパイル時間 14,483 ms
コンパイル使用メモリ 381,356 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-11-06 14:40:50
合計ジャッジ時間 16,907 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 18 ms
5,248 KB
testcase_16 AC 141 ms
7,324 KB
testcase_17 AC 56 ms
6,912 KB
testcase_18 AC 82 ms
7,936 KB
testcase_19 AC 187 ms
12,304 KB
testcase_20 AC 187 ms
12,304 KB
testcase_21 AC 175 ms
12,288 KB
testcase_22 AC 173 ms
12,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

fn main() {
    input! {
        n:usize,
        m:usize,
        uvw:[(usize,usize,usize);m],
        t:usize,
        r:[usize;t],
    }

    let mut ids_sorted_r = (0..t).collect::<Vec<_>>();
    ids_sorted_r.sort_by_key(|&i| r[i]);

    let mut ids_sorted_w = (0..m).collect::<Vec<_>>();
    ids_sorted_w.sort_by_key(|&i| uvw[i].2);

    let mut ans = vec![0; t];
    let mut uf = UnionFindTree::new(n);

    let mut id = 0;
    let mut cnt = n;
    for &i in ids_sorted_r.iter() {
        while id < m && uvw[ids_sorted_w[id]].2 <= r[i] {
            let (u, v, _) = uvw[ids_sorted_w[id]];
            if !uf.same(u, v) {
                uf.unite(u, v);
                cnt -= 1;
            }
            id += 1;
        }

        ans[i] = cnt;
    }

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

use unionfindtree::*;
mod unionfindtree {
    pub struct UnionFindTree {
        par: Vec<usize>,
        rank: Vec<usize>,
        size: Vec<usize>,
    }

    impl UnionFindTree {
        pub fn new(n: usize) -> Self {
            Self {
                par: (0..n).collect::<Vec<_>>(),
                rank: vec![0; n],
                size: vec![1; n],
            }
        }

        #[allow(dead_code)]
        pub fn same(&mut self, v1: usize, v2: usize) -> bool {
            self.root(v1) == self.root(v2)
        }

        #[allow(dead_code)]
        pub fn size(&mut self, v: usize) -> usize {
            let v_root = self.root(v);
            self.size[v_root]
        }

        #[allow(dead_code)]
        pub fn root(&mut self, v: usize) -> usize {
            if self.par[v] != v {
                self.par[v] = self.root(self.par[v]);
            }

            self.par[v]
        }

        pub fn unite(&mut self, v1: usize, v2: usize) {
            let mut v1_root = self.root(v1);
            let mut v2_root = self.root(v2);
            if v1_root == v2_root {
                return;
            }

            if self.rank[v1_root] < self.rank[v2_root] {
                std::mem::swap(&mut v1_root, &mut v2_root);
            }

            self.par[v2_root] = v1_root;
            self.size[v1_root] += self.size[v2_root];

            if self.rank[v1_root] == self.rank[v2_root] {
                self.rank[v1_root] += 1;
            }
        }

        #[allow(dead_code)]
        pub fn nofcc(&mut self) -> usize {
            let n = self.par.len();
            (0..n)
                .map(|v| self.root(v))
                .collect::<std::collections::HashSet<usize>>()
                .len()
        }
    }
}
0