#934625 (Rust) No.2563 色ごとのグループ

• 問題: No.2563 色ごとのグループ
• ユーザー: ikd
• 提出日時: 2023-12-02 15:36:29
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 135 ms / 2,000 ms
• コード長: 6,009 bytes
• コンパイル時間: 14,984 ms
• コンパイル使用メモリ: 378,240 KB
• 実行使用メモリ: 28,416 KB
• 最終ジャッジ日時: 2024-09-26 18:59:40
• 合計ジャッジ時間: 17,125 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	7 ms; 5,376 KB
testcase_21	AC	4 ms; 5,376 KB
testcase_22	AC	3 ms; 5,376 KB
testcase_23	AC	5 ms; 5,376 KB
testcase_24	AC	46 ms; 13,184 KB
testcase_25	AC	45 ms; 13,824 KB
testcase_26	AC	73 ms; 19,712 KB
testcase_27	AC	79 ms; 25,088 KB
testcase_28	AC	78 ms; 21,760 KB
testcase_29	AC	121 ms; 28,288 KB
testcase_30	AC	118 ms; 28,416 KB
testcase_31	AC	117 ms; 28,288 KB
testcase_32	AC	135 ms; 28,288 KB
testcase_33	AC	93 ms; 23,000 KB
testcase_34	AC	94 ms; 22,804 KB
testcase_35	AC	96 ms; 22,676 KB
testcase_36	AC	96 ms; 22,816 KB
testcase_37	AC	96 ms; 22,872 KB

ソースコード

pub use __cargo_equip::prelude::*;

use scanner::Scanner;
use std::{collections::HashSet, io};
use union_find::UnionFind;

fn main() {
    let mut scanner = Scanner::from(io::stdin().lock());
    let (n, m) = scan!((usize, usize), <~ scanner);
    let c = scan!([usize; n], <~ scanner);
    let edges = scan!([(usize, usize); m], <~ scanner);

    let c = c.into_iter().map(|c| c - 1).collect::<Vec<_>>();
    let edges = edges
        .into_iter()
        .map(|(u, v)| (u - 1, v - 1))
        .collect::<Vec<_>>();

    let mut sets = vec![HashSet::new(); n];
    for i in 0..n {
        sets[c[i]].insert(i);
    }
    let mut uf = UnionFind::new(n);
    for (u, v) in edges {
        if sets[c[u]].contains(&v) {
            uf.unite(u, v);
        }
    }
    let mut ans = 0;
    for set in sets {
        if set.is_empty() {
            continue;
        }
        let mut roots = Vec::new();
        for v in set {
            roots.push(uf.find(v));
        }
        roots.sort();
        roots.dedup();
        assert!(roots.len() >= 1);
        ans += roots.len() - 1;
    }
    println!("{}", ans);
}

// ✂ --- scanner --- ✂
#[allow(unused)]
mod scanner {
    pub use crate::__cargo_equip::prelude::*;

    use std::fmt;
    use std::io;
    use std::str;

    pub struct Scanner<R> {
        r: R,
        l: String,
        i: usize,
    }

    impl<R> Scanner<R>
    where
        R: io::BufRead,
    {
        pub fn new(reader: R) -> Self {
            Self {
                r: reader,
                l: String::new(),
                i: 0,
            }
        }

        pub fn scan<T>(&mut self) -> T
        where
            T: str::FromStr,
            T::Err: fmt::Debug,
        {
            self.skip_blanks();
            assert!(self.i < self.l.len()); // remain some character
            assert_ne!(&self.l[self.i..=self.i], " ");
            let rest = &self.l[self.i..];
            let len = rest
                .find(|ch| char::is_ascii_whitespace(&ch))
                .unwrap_or_else(|| rest.len());
            // parse self.l[self.i..(self.i + len)]
            let val = rest[..len]
                .parse()
                .unwrap_or_else(|e| panic!("{:?}, attempt to read `{}`", e, rest));
            self.i += len;
            val
        }

        pub fn scan_vec<T>(&mut self, n: usize) -> Vec<T>
        where
            T: str::FromStr,
            T::Err: fmt::Debug,
        {
            (0..n).map(|_| self.scan()).collect::<Vec<_>>()
        }

        fn skip_blanks(&mut self) {
            loop {
                match self.l[self.i..].find(|ch| !char::is_ascii_whitespace(&ch)) {
                    Some(j) => {
                        self.i += j;
                        break;
                    }
                    None => {
                        self.l.clear(); // clear buffer
                        let num_bytes = self
                            .r
                            .read_line(&mut self.l)
                            .unwrap_or_else(|_| panic!("invalid UTF-8"));
                        assert!(num_bytes > 0, "reached EOF :(");
                        self.i = 0;
                    }
                }
            }
        }
    }

    impl<'a> From<&'a str> for Scanner<&'a [u8]> {
        fn from(s: &'a str) -> Self {
            Self::new(s.as_bytes())
        }
    }

    impl<'a> From<io::StdinLock<'a>> for Scanner<io::BufReader<io::StdinLock<'a>>> {
        fn from(stdin: io::StdinLock<'a>) -> Self {
            Self::new(io::BufReader::new(stdin))
        }
    }

    #[macro_export]
    macro_rules! scan {
        (( $($t: ty),+ ), <~ $scanner: expr) => {
            ( $(scan!($t, <~ $scanner)),+ )
        };
        ([ $t: tt; $n: expr ], <~ $scanner: expr) => {
            (0..$n).map(|_| scan!($t, <~ $scanner)).collect::<Vec<_>>()
        };
        ($t: ty, <~ $scanner: expr) => {
            $scanner.scan::<$t>()
        };
    }
}
// ✂ --- scanner --- ✂

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
///
///  - `union_find 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#f49de25336b2de6602bce284a44ec4b9d163e9f4)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::union_find`
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod union_find {
            pub struct UnionFind {
                par: Vec<usize>,
                size: Vec<usize>,
            }

            impl UnionFind {
                pub fn new(n: usize) -> UnionFind {
                    UnionFind {
                        par: (0..n).collect(),
                        size: vec![1; n],
                    }
                }

                pub fn find(&mut self, i: usize) -> usize {
                    if self.par[i] != i {
                        self.par[i] = self.find(self.par[i]);
                    }
                    self.par[i]
                }

                pub fn unite(&mut self, i: usize, j: usize) {
                    let i = self.find(i);
                    let j = self.find(j);
                    if i == j {
                        return;
                    }
                    let (i, j) = if self.size[i] >= self.size[j] {
                        (i, j)
                    } else {
                        (j, i)
                    };
                    self.par[j] = i;
                    self.size[i] += self.size[j];
                }

                pub fn get_size(&mut self, i: usize) -> usize {
                    let p = self.find(i);
                    self.size[p]
                }

                pub fn same(&mut self, i: usize, j: usize) -> bool {
                    self.find(i) == self.find(j)
                }
            }
        }
    }

    pub(crate) mod macros {
        pub mod union_find {}
    }

    pub(crate) mod prelude {
        pub use crate::__cargo_equip::crates::*;
    }

    mod preludes {
        pub mod union_find {}
    }
}