結果

問題 No.697 池の数はいくつか
ユーザー くれちーくれちー
提出日時 2018-06-09 18:26:45
言語 Rust
(1.77.0)
結果
AC  
実行時間 335 ms / 6,000 ms
コード長 7,818 bytes
コンパイル時間 964 ms
コンパイル使用メモリ 176,072 KB
実行使用メモリ 151,400 KB
最終ジャッジ日時 2024-04-25 19:53:43
合計ジャッジ時間 5,069 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 0 ms
6,812 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 0 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 0 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 0 ms
6,940 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 0 ms
6,940 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 0 ms
6,940 KB
testcase_21 AC 0 ms
6,940 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 32 ms
18,284 KB
testcase_25 AC 34 ms
18,436 KB
testcase_26 AC 30 ms
18,528 KB
testcase_27 AC 30 ms
18,436 KB
testcase_28 AC 30 ms
18,512 KB
testcase_29 AC 292 ms
151,272 KB
testcase_30 AC 335 ms
151,296 KB
testcase_31 AC 277 ms
151,248 KB
testcase_32 AC 302 ms
151,400 KB
testcase_33 AC 282 ms
151,260 KB
testcase_34 AC 286 ms
151,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn solve<R: BufRead, W: Write>(_reader: R, _writer: &mut W) {
  let mut _scanner = Scanner::new(_reader);

  #[allow(unused_macros)]
  macro_rules! scan {
    ($t:ty) => {
      _scanner.next::<$t>().unwrap()
    };
    ($($t:ty),+) => {
      ($(scan!($t)),+)
    };
    ($t:ty; $n:expr) => {
      scan_iter!($t; $n).collect::<Vec<_>>()
    };
    ($t_0:ty, $t_1:ty; $n:expr) => {
      scan!($t_0 = 0, $t_1 = 1; $n)
    };
    ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => {
      scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n)
    };
    ($($t:ty = $i:tt),+; $n:expr) => {{
      let mut vecs = ($(Vec::<$t>::with_capacity($n)),+);
      for _ in 0..$n {$(
        vecs.$i.push(scan!($t));
      )+}
      vecs
    }};
  }

  #[allow(unused_macros)]
  macro_rules! scan_iter {
    ($t:ty; $n:expr) => {
      _scanner.take::<$t>($n).map(|x| x.unwrap())
    };
  }

  #[allow(unused_macros)]
  macro_rules! print {
    ($fmt:expr) => {
      write!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      write!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! println {
    () => {
      writeln!(_writer).unwrap()
    };
    ($fmt:expr) => {
      writeln!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      writeln!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  use data_structures::UnionFindTree;

  const DY: [usize; 2] = [0, 1];
  const DX: [usize; 2] = [1, 0];

  let (h, w) = scan!(usize, usize);
  let field = scan!(u8; h * w);
  let mut uf = UnionFindTree::new(h * w);
  let index = |y, x| y * w + x;
  let mut ans = field.iter().filter(|&&x| x == b'1').count();

  for i in 0..h {
    for j in 0..w {
      if field[index(i, j)] == b'1' {
        for (&dy, &dx) in DY.iter().zip(DX.iter()) {
          let (y, x) = (i + dy, j + dx);
          if y < h && x < w && field[index(y, x)] == b'1' {
            if uf.unite(index(i, j), index(y, x)) {
              ans -= 1;
            }
          }
        }
      }
    }
  }

  println!("{}", ans);
}

fn main() {
  let stdin = stdin();
  let stdout = stdout();
  #[cfg(debug_assertions)]
  let mut writer = stdout.lock();
  #[cfg(not(debug_assertions))]
  let mut writer = ::std::io::BufWriter::new(stdout.lock());
  solve(stdin.lock(), &mut writer);
  writer.flush().unwrap();
}

use io::Scanner;
use std::io::{stdin, stdout, BufRead, Write};

pub mod data_structures {
  pub use self::union_find_tree::*;

  mod union_find_tree {
    use std::mem::swap;

    pub struct UnionFindTree {
      nodes: Vec<Node>,
    }

    #[derive(Clone, Copy)]
    enum Node {
      Root { node_count: usize },
      Descendant { parent_index: usize },
    }

    impl UnionFindTree {
      pub fn new(size: usize) -> Self {
        UnionFindTree {
          nodes: vec![Node::Root { node_count: 1 }; size],
        }
      }

      pub fn len(&self) -> usize {
        self.nodes.len()
      }

      pub fn unite(&mut self, l_index: usize, r_index: usize) -> bool {
        debug_assert!(l_index < self.len());
        debug_assert!(r_index < self.len());
        let mut l_root_index = self.find(l_index);
        let mut r_root_index = self.find(r_index);
        if l_root_index == r_root_index {
          return false;
        }
        match (self.nodes[l_root_index], self.nodes[r_root_index]) {
          (Node::Root { node_count: l_node_count }, Node::Root { node_count: r_node_count }) => {
            let node_count = l_node_count + r_node_count;
            if l_node_count < r_node_count {
              swap(&mut l_root_index, &mut r_root_index);
            }
            self.nodes[l_root_index] = Node::Root { node_count: node_count };
            self.nodes[r_root_index] = Node::Descendant { parent_index: l_root_index };
          }
          _ => unreachable!("`find` must return root index"),
        }
        true
      }

      pub fn find(&mut self, index: usize) -> usize {
        debug_assert!(index < self.len());
        match self.nodes[index] {
          Node::Root { .. } => index,
          Node::Descendant { parent_index } => {
            let root_index = self.find(parent_index);
            debug_assert!(match self.nodes[parent_index] {
              Node::Root { .. } => true,
              Node::Descendant { parent_index: parent_parent_index } => match self.nodes[parent_parent_index] {
                Node::Root { .. } => true,
                Node::Descendant { .. } => false,
              },
            });
            self.nodes[index] = Node::Descendant { parent_index: root_index };
            root_index
          }
        }
      }

      pub fn is_same_group(&mut self, l_index: usize, r_index: usize) -> bool {
        debug_assert!(l_index < self.len());
        debug_assert!(r_index < self.len());
        self.find(l_index) == self.find(r_index)
      }

      pub fn count_elements(&mut self, index: usize) -> usize {
        debug_assert!(index < self.len());
        let root_index = self.find(index);
        match self.nodes[root_index] {
          Node::Root { node_count } => node_count,
          _ => unreachable!("`find` must return root index"),
        }
      }
    }
  }
}

pub mod io {
  pub use self::scanner::*;

  mod scanner {
    use std::io::BufRead;
    use std::marker::PhantomData;
    use std::str::{from_utf8, FromStr};

    pub struct Scanner<R> {
      reader: R,
      buffer: Vec<u8>,
      position: usize,
    }

    impl<R: BufRead> Scanner<R> {
      pub fn new(reader: R) -> Self {
        Scanner { reader: reader, buffer: vec![], position: 0 }
      }

      pub fn next<T: Parse>(&mut self) -> Option<T> {
        Parse::parse(self.next_bytes().unwrap_or(&[]))
      }

      pub fn take<T: Parse>(&mut self, n: usize) -> Take<R, T> {
        Take { scanner: self, n: n, _marker: PhantomData }
      }

      pub fn next_bytes(&mut self) -> Option<&[u8]> {
        if self.buffer.is_empty() {
          self.read_line();
        }
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') => self.position += 1,
            Some(&b'\n') => self.read_line(),
            Some(_) => break,
            None => return None,
          }
        }
        let start = self.position;
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') | Some(&b'\n') | None => break,
            Some(_) => self.position += 1,
          }
        }
        Some(&self.buffer[start..self.position])
      }

      fn read_line(&mut self) {
        self.position = 0;
        self.buffer.clear();
        self.reader.read_until(b'\n', &mut self.buffer).unwrap();
      }
    }

    pub struct Take<'a, R: 'a, T> {
      scanner: &'a mut Scanner<R>,
      n: usize,
      _marker: PhantomData<fn() -> T>,
    }

    impl<'a, R: BufRead, T: Parse> Iterator for Take<'a, R, T> {
      type Item = Option<T>;

      fn next(&mut self) -> Option<Self::Item> {
        if self.n > 0 {
          self.n -= 1;
          Some(self.scanner.next())
        } else {
          None
        }
      }

      fn size_hint(&self) -> (usize, Option<usize>) {
        (self.n, Some(self.n))
      }
    }

    impl<'a, R: BufRead, T: Parse> ExactSizeIterator for Take<'a, R, T> {}

    pub trait Parse: Sized {
      fn parse(bytes: &[u8]) -> Option<Self>;
    }

    impl Parse for u8 {
      fn parse(bytes: &[u8]) -> Option<Self> {
        if bytes.len() == 1 {
          Some(*unsafe { bytes.get_unchecked(0) })
        } else {
          None
        }
      }
    }

    macro_rules! parse_impl {
      ($($t:ident)+) => {$(
        impl Parse for $t {
          fn parse(bytes: &[u8]) -> Option<Self> {
            from_utf8(bytes).ok().and_then(|s| $t::from_str(s).ok())
          }
        }
      )+};
    }

    parse_impl! { i32 i64 isize u32 u64 usize String }
  }
}
0