結果
問題 | No.2354 Poor Sight in Winter |
ユーザー | koba-e964 |
提出日時 | 2023-06-16 23:34:45 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 2,331 bytes |
コンパイル時間 | 29,939 ms |
コンパイル使用メモリ | 379,316 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 16:51:25 |
合計ジャッジ時間 | 15,164 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 17 ms
5,376 KB |
testcase_12 | AC | 13 ms
5,376 KB |
testcase_13 | AC | 28 ms
5,376 KB |
testcase_14 | AC | 30 ms
5,376 KB |
testcase_15 | AC | 26 ms
5,376 KB |
testcase_16 | AC | 27 ms
5,376 KB |
testcase_17 | AC | 29 ms
5,376 KB |
testcase_18 | AC | 9 ms
5,376 KB |
testcase_19 | AC | 19 ms
5,376 KB |
testcase_20 | AC | 10 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 6 ms
5,376 KB |
testcase_23 | AC | 6 ms
5,376 KB |
testcase_24 | AC | 16 ms
5,376 KB |
testcase_25 | AC | 4 ms
5,376 KB |
testcase_26 | AC | 3 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
ソースコード
use std::cmp::*; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } // https://yukicoder.me/problems/no/2354 (3) // 二分探索して最短路 (必要な明かりの個数を距離とする) // Tags: dijkstra-in-dense-graphs fn main() { input! { n: usize, k: i64, xy: [(i64, i64); n + 2], } let dist = |i: usize, j: usize| { let (xi, yi) = xy[i]; let (xj, yj) = xy[j]; (xi - xj).abs() + (yi - yj).abs() }; let mut pass = dist(0, 1); let mut fail = 0; while pass - fail > 1 { const INF: i64 = 1 << 50; let mid = (pass + fail) / 2; let mut tbl = vec![INF; n + 2]; let mut dec = vec![false; n + 2]; let mut rem = n + 2; tbl[0] = 0; // O(n^2) while rem > 0 { let mut mi = (INF, 0); for i in 0..n + 2 { if !dec[i] { mi = min(mi, (tbl[i], i)); } } let now = mi.1; dec[now] = true; rem -= 1; for i in 0..n + 2 { if dec[i] { continue; } let d = dist(now, i); tbl[i] = min(tbl[i], mi.0 + (d - 1) / mid); } } if tbl[1] <= k { pass = mid; } else { fail = mid; } } println!("{}", pass); }