結果

問題 No.1390 Get together
ユーザー StrorkisStrorkis
提出日時 2021-02-12 21:43:26
言語 Rust
(1.77.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,227 bytes
コンパイル時間 4,564 ms
コンパイル使用メモリ 116,856 KB
最終ジャッジ日時 2023-09-27 03:27:53
合計ジャッジ時間 5,447 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
error: format argument must be a string literal
  --> Main.rs:18:34
   |
18 |                 Err(e) => panic!(e), 
   |                                  ^
   |
help: you might be missing a string literal to format with
   |
18 |                 Err(e) => panic!("{}", e), 
   |                                  +++++

error: aborting due to previous error

ソースコード

diff # 

mod io {
    #[macro_export]
    macro_rules! scan {
        ($r:expr, [$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($r, $t)).collect::<Vec<_>>());
        ($r:expr, ($($t:tt),*)) => (($(scan!($r, $t)),*));
        ($r:expr, [u8]) => (io::scan($r).into_bytes());
        ($r:expr, $t:ty) => (io::scan($r).parse::<$t>().unwrap());
    }

    use std::io::{BufRead, ErrorKind};

    pub fn scan<R: BufRead>(r: &mut R) -> String {
        let mut res = Vec::new();
        loop {
            let buf = match r.fill_buf() {
                Ok(buf) => buf,
                Err(e) if e.kind() == ErrorKind::Interrupted => continue,
                Err(e) => panic!(e), 
            };
            let (done, used) = match buf.iter().position(u8::is_ascii_whitespace) {
                Some(i) => {
                    res.extend_from_slice(&buf[..i]);
                    (res.len() > 0, i + 1)
                }
                None => {
                    res.extend_from_slice(buf);
                    (false, buf.len())
                }
            };
            r.consume(used);
            if done || used == 0 {
                return res.into_iter().map(char::from).collect();
            }
        }
    }
}

#[allow(dead_code)]
mod dsu {
    // reference: https://github.com/atcoder/ac-library
    pub struct Dsu {
        n: usize,
        parent_or_size: Vec<usize>,
    }

    impl Dsu {
        pub fn new(n: usize) -> Dsu {
            Dsu { n, parent_or_size: vec![!1; n] }
        }

        pub fn merge(&mut self, a: usize, b: usize) -> usize {
            let (mut x, mut y) = (self.leader(a), self.leader(b));
            if x == y { return x; }
            if !self.parent_or_size[x] < !self.parent_or_size[y] {
                std::mem::swap(&mut x, &mut y);
            }
            self.parent_or_size[x] -= !self.parent_or_size[y];
            self.parent_or_size[y] = x;
            x
        }

        pub fn same(&mut self, a: usize, b: usize) -> bool {
            self.leader(a) == self.leader(b)
        }

        pub fn leader(&mut self, a: usize) -> usize {
            if self.parent_or_size[a] >= self.n { return a; }
            self.parent_or_size[a] = self.leader(self.parent_or_size[a]);
            self.parent_or_size[a]
        }

        pub fn size(&mut self, a: usize) -> usize {
            let x = self.leader(a);
            !self.parent_or_size[x]
        }
    }    
}

use std::io::{BufRead, Write};
use dsu::Dsu;

fn run<R: BufRead, W: Write>(reader: &mut R, writer: &mut W) {
    let (n, m) = scan!(reader, (usize, usize));

    let mut dsu = Dsu::new(m + 1);
    let mut colors = vec![0; n + 1];
    for _ in 0..n {
        let (b, c) = scan!(reader, (usize, usize));
        if colors[c] > 0 {
            dsu.merge(colors[c], b);
        }
        colors[c] = b;
    }

    let mut ans = 0;
    for i in 1..=m {
        if i == dsu.leader(i) {
            ans += dsu.size(i) - 1;
        }
    }
    writeln!(writer, "{}", ans).ok();
}

fn main() {
    let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let mut reader = std::io::BufReader::new(stdin.lock());
    let mut writer = std::io::BufWriter::new(stdout.lock());
    run(&mut reader, &mut writer);
}
0