結果

問題 No.2290 UnUnion Find
ユーザー Yukino DX.Yukino DX.
提出日時 2024-09-13 22:35:11
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 542 ms / 2,000 ms
コード長 2,964 bytes
コンパイル時間 15,405 ms
コンパイル使用メモリ 378,020 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-09-13 22:35:47
合計ジャッジ時間 33,108 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 322 ms
5,376 KB
testcase_03 AC 212 ms
6,784 KB
testcase_04 AC 335 ms
6,912 KB
testcase_05 AC 297 ms
6,784 KB
testcase_06 AC 542 ms
6,784 KB
testcase_07 AC 516 ms
6,912 KB
testcase_08 AC 259 ms
6,784 KB
testcase_09 AC 300 ms
6,912 KB
testcase_10 AC 231 ms
6,784 KB
testcase_11 AC 458 ms
6,784 KB
testcase_12 AC 395 ms
6,784 KB
testcase_13 AC 377 ms
6,784 KB
testcase_14 AC 262 ms
6,784 KB
testcase_15 AC 401 ms
6,784 KB
testcase_16 AC 335 ms
6,784 KB
testcase_17 AC 222 ms
6,912 KB
testcase_18 AC 182 ms
6,912 KB
testcase_19 AC 202 ms
7,936 KB
testcase_20 AC 209 ms
11,264 KB
testcase_21 AC 252 ms
5,376 KB
testcase_22 AC 226 ms
5,504 KB
testcase_23 AC 228 ms
5,632 KB
testcase_24 AC 214 ms
9,856 KB
testcase_25 AC 256 ms
5,376 KB
testcase_26 AC 210 ms
10,624 KB
testcase_27 AC 208 ms
10,112 KB
testcase_28 AC 219 ms
7,168 KB
testcase_29 AC 213 ms
9,728 KB
testcase_30 AC 254 ms
5,376 KB
testcase_31 AC 209 ms
9,216 KB
testcase_32 AC 244 ms
5,376 KB
testcase_33 AC 211 ms
6,912 KB
testcase_34 AC 213 ms
11,264 KB
testcase_35 AC 212 ms
10,496 KB
testcase_36 AC 241 ms
5,376 KB
testcase_37 AC 229 ms
6,656 KB
testcase_38 AC 237 ms
5,376 KB
testcase_39 AC 225 ms
5,632 KB
testcase_40 AC 212 ms
10,240 KB
testcase_41 AC 275 ms
5,376 KB
testcase_42 AC 207 ms
7,808 KB
testcase_43 AC 201 ms
7,552 KB
testcase_44 AC 333 ms
6,784 KB
testcase_45 AC 174 ms
6,912 KB
testcase_46 AC 178 ms
6,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashSet;

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

fn main() {
    input! {
        n:usize,
        q:usize,
    }

    let mut uf = UnionFindTree::new(n);
    let mut leaders = (0..n).collect::<HashSet<_>>();
    for _ in 0..q {
        input! {
            t:usize,
        }

        if t == 1 {
            input! {
                u:Usize1,
                v:Usize1,
            }

            if !uf.same(u, v) {
                let leader_u = uf.root(u);
                let leader_v = uf.root(v);
                uf.unite(u, v);
                if uf.root(u) == leader_u {
                    leaders.remove(&leader_v);
                } else {
                    leaders.remove(&leader_u);
                }
            }
        } else {
            input! {
                v:Usize1,
            }

            if uf.size(v) == n {
                println!("-1");
            } else {
                let leader_v = uf.root(v);
                let ans = *leaders
                    .iter()
                    .filter(|leader| leader_v != **leader)
                    .next()
                    .unwrap();
                println!("{}", ans + 1);
            }
        }
    }
}

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