結果
問題 | No.2731 Two Colors |
ユーザー | magurofly |
提出日時 | 2024-04-19 21:56:43 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 166 ms / 3,000 ms |
コード長 | 1,870 bytes |
コンパイル時間 | 3,215 ms |
コンパイル使用メモリ | 146,580 KB |
実行使用メモリ | 14,080 KB |
最終ジャッジ日時 | 2024-04-19 21:57:11 |
合計ジャッジ時間 | 6,306 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 160 ms
11,136 KB |
testcase_01 | AC | 166 ms
11,136 KB |
testcase_02 | AC | 162 ms
11,136 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 5 ms
5,376 KB |
testcase_05 | AC | 5 ms
5,376 KB |
testcase_06 | AC | 14 ms
5,376 KB |
testcase_07 | AC | 14 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 51 ms
12,064 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 70 ms
12,784 KB |
testcase_12 | AC | 54 ms
12,032 KB |
testcase_13 | AC | 58 ms
11,380 KB |
testcase_14 | AC | 24 ms
7,040 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 27 ms
6,528 KB |
testcase_17 | AC | 33 ms
8,768 KB |
testcase_18 | AC | 7 ms
5,376 KB |
testcase_19 | AC | 29 ms
6,400 KB |
testcase_20 | AC | 31 ms
9,236 KB |
testcase_21 | AC | 8 ms
5,376 KB |
testcase_22 | AC | 58 ms
12,288 KB |
testcase_23 | AC | 16 ms
5,376 KB |
testcase_24 | AC | 10 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 42 ms
9,948 KB |
testcase_27 | AC | 57 ms
13,824 KB |
testcase_28 | AC | 45 ms
9,856 KB |
testcase_29 | AC | 14 ms
5,376 KB |
testcase_30 | AC | 21 ms
6,104 KB |
testcase_31 | AC | 18 ms
5,376 KB |
testcase_32 | AC | 79 ms
14,080 KB |
testcase_33 | AC | 1 ms
5,376 KB |
testcase_34 | AC | 0 ms
5,376 KB |
testcase_35 | AC | 1 ms
5,376 KB |
ソースコード
#![allow(dead_code, unused_imports, unused_macros, non_snake_case)] fn main() { let [H, W] = read_words::<usize>()[..] else { return }; let A = (0 .. H).map(|_| read_words::<usize>() ).collect::<Vec<_>>(); let mut colors = vec![vec![None; W]; H]; colors[0][0] = Some(true); colors[H - 1][W - 1] = Some(false); let mut pq = vec![BinaryHeap::new(); 2]; for &(i, j, c) in &[(0, 0, 1), (H - 1, W - 1, 0)] { neighbor4(i, j, H, W, |i2, j2| { if colors[i2][j2].is_none() { pq[c].push((Reverse(A[i2][j2]), i2, j2)); } }); } let mut ans = 0; 'main_loop: for t in 1 ..= H * W - 2 { let c = t % 2; while let Some((_, i, j)) = pq[c].pop() { if colors[i][j].is_some() { continue; } let mut fin = false; ans += 1; colors[i][j] = Some(c == 1); neighbor4(i, j, H, W, |i2, j2| { if colors[i2][j2].is_none() { pq[c].push((Reverse(A[i2][j2]), i2, j2)); } else if colors[i2][j2] != colors[i][j] { fin = true; } }); if fin { break 'main_loop; } break; } } println!("{}", ans); } type Int = i64; const MOD: Int = 1_000_000_007; const INF: Int = 1_000_000_000; const YESNO: [&'static str; 2] = ["Yes", "No"]; use std::collections::*; use std::cmp::Reverse; fn read_line() -> String { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).ok(); buf } fn read_words<T: std::str::FromStr>() -> Vec<T> where T::Err: std::fmt::Debug { read_line().split_whitespace().map(|x| T::from_str(x).unwrap() ).collect() } fn yes() { println!("{}", YESNO[0]); } fn no() { println!("{}", YESNO[1]); } fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); } fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }