結果
問題 | No.697 池の数はいくつか |
ユーザー | masaki.arizuka |
提出日時 | 2019-09-22 23:47:05 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 1,844 ms / 6,000 ms |
コード長 | 3,377 bytes |
コンパイル時間 | 1,583 ms |
コンパイル使用メモリ | 178,976 KB |
実行使用メモリ | 213,096 KB |
最終ジャッジ日時 | 2024-04-25 20:34:53 |
合計ジャッジ時間 | 15,096 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 0 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,944 KB |
testcase_07 | AC | 0 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 1 ms
6,944 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,944 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 0 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 1 ms
6,940 KB |
testcase_22 | AC | 0 ms
6,940 KB |
testcase_23 | AC | 1 ms
6,940 KB |
testcase_24 | AC | 163 ms
23,168 KB |
testcase_25 | AC | 176 ms
23,152 KB |
testcase_26 | AC | 161 ms
23,416 KB |
testcase_27 | AC | 161 ms
23,224 KB |
testcase_28 | AC | 173 ms
23,184 KB |
testcase_29 | AC | 1,645 ms
213,020 KB |
testcase_30 | AC | 1,607 ms
194,304 KB |
testcase_31 | AC | 1,844 ms
213,096 KB |
testcase_32 | AC | 1,581 ms
193,160 KB |
testcase_33 | AC | 1,591 ms
192,584 KB |
testcase_34 | AC | 1,551 ms
194,836 KB |
コンパイルメッセージ
warning: unused import: `std::collections::VecDeque` --> main.rs:65:9 | 65 | use std::collections::VecDeque; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: 1 warning emitted
ソースコード
#[allow(unused_macros)] macro_rules! debug { ($($a:expr),*) => { #[cfg(debug_assertions)] writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*); } } #[allow(unused_imports)] use std::cmp::{min, max}; #[allow(unused_imports)] use std::io::{stdout, stdin, BufWriter, Write}; #[derive(Debug)] pub struct UnionFind { par: Vec<usize>, } impl UnionFind { pub fn new(n: usize) -> UnionFind { let mut vec = vec![0; n]; for i in 0..n { vec[i] = i; } UnionFind { par: vec } } pub fn find(&mut self, x: usize) -> usize { if x == self.par[x] { x } else { let par = self.par[x]; let res = self.find(par); self.par[x] = res; res } } pub fn same(&mut self, a: usize, b: usize) -> bool { self.find(a) == self.find(b) } pub fn unite(&mut self, a: usize, b: usize) { let apar = self.find(a); let bpar = self.find(b); self.par[apar] = bpar; } } fn main() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($($format:tt)*) => (write!(out,$($format)*).unwrap()); } let stdin = std::io::stdin(); let mut sc = Scanner { reader: stdin.lock() }; let h:usize = sc.read(); let w:usize = sc.read(); let mut f = vec![]; for _ in 0..h { let r:Vec<usize> = sc.read_vec(w); f.push(r); } use std::collections::VecDeque; let mut uf = UnionFind::new(h*w); for x in 0..h { for y in 0..w { if f[x][y] == 0 { continue; } let x = x as i64; let y = y as i64; let ds = vec![ (x+1, y), (x, y+1), (x-1, y), (x, y-1), ]; for (nx, ny) in ds { if nx < 0 || ny < 0 { continue; } let x = x as usize; let y = y as usize; let nx = nx as usize; let ny = ny as usize; if nx >= h || ny >= w { continue; } if f[nx][ny] == 0 { continue; } uf.unite(x*w+y, nx*w+ny); } } } let mut ans = vec![]; for x in 0..h { for y in 0..w { if f[x][y] == 1 { ans.push(uf.find(x*w+y)); } } } ans.sort(); ans.dedup(); puts!("{}\n", ans.len()); } pub struct Scanner<R> { reader: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf: String = self .reader .by_ref() .bytes() .map(|b| b.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect(); buf.parse::<T>().ok().expect("Parse error.") } pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }