結果
問題 | No.1473 おでぶなおばけさん |
ユーザー | mai |
提出日時 | 2021-04-22 02:34:13 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 2,998 bytes |
コンパイル時間 | 794 ms |
コンパイル使用メモリ | 152,176 KB |
実行使用メモリ | 12,512 KB |
最終ジャッジ日時 | 2023-09-17 09:49:29 |
合計ジャッジ時間 | 6,791 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 151 ms
11,844 KB |
testcase_03 | AC | 108 ms
10,392 KB |
testcase_04 | AC | 77 ms
7,380 KB |
testcase_05 | AC | 30 ms
4,376 KB |
testcase_06 | AC | 152 ms
10,340 KB |
testcase_07 | AC | 146 ms
12,388 KB |
testcase_08 | AC | 218 ms
12,512 KB |
testcase_09 | AC | 149 ms
12,512 KB |
testcase_10 | AC | 57 ms
6,180 KB |
testcase_11 | AC | 61 ms
7,708 KB |
testcase_12 | AC | 58 ms
6,940 KB |
testcase_13 | AC | 34 ms
4,908 KB |
testcase_14 | AC | 24 ms
4,380 KB |
testcase_15 | AC | 49 ms
6,584 KB |
testcase_16 | AC | 52 ms
5,440 KB |
testcase_17 | AC | 5 ms
4,376 KB |
testcase_18 | AC | 7 ms
4,376 KB |
testcase_19 | AC | 49 ms
6,232 KB |
testcase_20 | AC | 76 ms
9,296 KB |
testcase_21 | AC | 94 ms
8,040 KB |
testcase_22 | AC | 73 ms
10,136 KB |
testcase_23 | AC | 64 ms
9,860 KB |
testcase_24 | AC | 62 ms
8,916 KB |
testcase_25 | AC | 128 ms
9,916 KB |
testcase_26 | AC | 102 ms
9,908 KB |
testcase_27 | AC | 41 ms
4,532 KB |
testcase_28 | AC | 140 ms
12,372 KB |
testcase_29 | AC | 102 ms
8,400 KB |
testcase_30 | AC | 136 ms
9,340 KB |
testcase_31 | AC | 119 ms
11,988 KB |
testcase_32 | AC | 113 ms
10,744 KB |
testcase_33 | AC | 70 ms
8,916 KB |
testcase_34 | AC | 31 ms
5,748 KB |
testcase_35 | AC | 42 ms
5,588 KB |
testcase_36 | AC | 85 ms
6,996 KB |
testcase_37 | AC | 76 ms
9,192 KB |
testcase_38 | AC | 13 ms
4,380 KB |
testcase_39 | AC | 54 ms
5,564 KB |
testcase_40 | AC | 55 ms
5,520 KB |
testcase_41 | AC | 47 ms
5,196 KB |
testcase_42 | AC | 47 ms
5,208 KB |
testcase_43 | AC | 63 ms
9,192 KB |
testcase_44 | AC | 63 ms
9,224 KB |
testcase_45 | AC | 63 ms
9,244 KB |
testcase_46 | AC | 93 ms
7,944 KB |
testcase_47 | AC | 120 ms
9,512 KB |
testcase_48 | AC | 120 ms
9,324 KB |
ソースコード
use std::{collections::*, io::Read}; fn take_token<R: std::io::BufRead>(cin: &mut R) -> String { cin.bytes() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::<String>() } #[allow(unused)] macro_rules! scan { ($io:expr => $t:ty) => (take_token(&mut $io).parse::<$t>().unwrap()); ($io:expr => $t:tt * $n:expr) => ((0..$n).map(|_| scan!($io => $t)).collect::<Vec<_>>()); ($io:expr => $($t:tt),*) => (($(scan!($io => $t)),*)); ($io:expr => $($t:tt),* * $n:expr) => ((0..$n).map(|_| ($(scan!($io => $t)),*)).collect::<Vec<_>>()); } struct Graph<T: Clone = ()>(Vec<Vec<(usize, T)>>); impl<T: Clone> Graph<T> { fn to<'a>(&self, i: usize) -> &Vec<(usize, T)> { &(self.0)[i] } } struct GraphBuilder<T: Clone = ()>(Graph<T>); impl<T: Clone> GraphBuilder<T> { fn new(n: usize) -> Self { Self(Graph::<T>(vec![Vec::<(usize, T)>::new(); n])) } fn connect(&mut self, u: usize, v: usize, item: T) { (self.0 .0)[u].push((v, item.clone())); (self.0 .0)[v].push((u, item)); } fn build(self) -> Graph<T> { self.0 } } // macro_rules! binary_search { // ($ok:expr, $ng:expr, $m:pat => $b:expr) => {{ // let mut (ok, ng) = ($ok, $ng); // while (ok - ng).abs() > 1 { // let $m = (ok + ng) / 2; // if $b { // ok = $m; // } else { // ng = $m; // } // } // ok // }}; // } fn main() { solve(std::io::stdin().lock()) } fn calc(graph: &Graph<i32>, n: usize, k: i32) -> Option<i32> { let mut visited = vec![0; n as usize]; let mut que = VecDeque::<usize>::new(); que.push_back(0); while let Some(v) = que.pop_front() { let d = visited[v]; if v == n - 1 { return Some(d); } for (v2, cap) in graph.to(v).iter() { if *cap < k || visited[*v2] > 0 { continue; } visited[*v2] = d + 1; que.push_back(*v2); } } None } fn solve<R: std::io::BufRead>(mut cin: R) { let (n, m) = scan!(cin => i32, i32); let mut builder = GraphBuilder::<i32>::new(n as usize); for _ in 0..m { let (u, v, m) = scan!(cin => i32, i32, i32); builder.connect((u - 1) as usize, (v - 1) as usize, m); } let graph = builder.build(); let k = { let mut ok = 0 as i32; let mut ng = i32::max_value() / 2; while (ok - ng).abs() > 1 { let m = (ok + ng) / 2; if calc(&graph, n as usize, m).is_some() { ok = m; } else { ng = m; } } ok }; // let k = // binary_search!(0 as i32, i32::max_value()/2, k => calc(&graph, n as usize, k).is_some()); println!("{} {}", k, calc(&graph, n as usize, k).unwrap()); // panic!("non-connective"); }