結果

問題 No.1473 おでぶなおばけさん
ユーザー maimai
提出日時 2021-04-23 01:18:04
言語 Rust
(1.77.0)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 2,583 bytes
コンパイル時間 4,431 ms
コンパイル使用メモリ 153,056 KB
実行使用メモリ 12,564 KB
最終ジャッジ日時 2023-09-17 10:25:48
合計ジャッジ時間 7,298 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 157 ms
11,940 KB
testcase_03 AC 108 ms
10,376 KB
testcase_04 AC 80 ms
7,484 KB
testcase_05 AC 32 ms
4,376 KB
testcase_06 AC 148 ms
10,444 KB
testcase_07 AC 157 ms
12,548 KB
testcase_08 AC 215 ms
12,564 KB
testcase_09 AC 139 ms
12,488 KB
testcase_10 AC 57 ms
6,192 KB
testcase_11 AC 61 ms
7,748 KB
testcase_12 AC 57 ms
6,940 KB
testcase_13 AC 34 ms
4,952 KB
testcase_14 AC 24 ms
4,376 KB
testcase_15 AC 51 ms
6,624 KB
testcase_16 AC 55 ms
5,472 KB
testcase_17 AC 4 ms
4,380 KB
testcase_18 AC 8 ms
4,380 KB
testcase_19 AC 49 ms
6,392 KB
testcase_20 AC 78 ms
9,404 KB
testcase_21 AC 97 ms
8,164 KB
testcase_22 AC 71 ms
10,188 KB
testcase_23 AC 63 ms
9,856 KB
testcase_24 AC 59 ms
8,892 KB
testcase_25 AC 97 ms
10,028 KB
testcase_26 AC 96 ms
9,844 KB
testcase_27 AC 35 ms
4,572 KB
testcase_28 AC 129 ms
12,388 KB
testcase_29 AC 101 ms
8,420 KB
testcase_30 AC 133 ms
9,296 KB
testcase_31 AC 124 ms
12,028 KB
testcase_32 AC 104 ms
10,784 KB
testcase_33 AC 72 ms
8,972 KB
testcase_34 AC 32 ms
5,760 KB
testcase_35 AC 43 ms
5,668 KB
testcase_36 AC 93 ms
7,036 KB
testcase_37 AC 79 ms
9,276 KB
testcase_38 AC 13 ms
4,380 KB
testcase_39 AC 54 ms
5,576 KB
testcase_40 AC 54 ms
5,636 KB
testcase_41 AC 48 ms
5,192 KB
testcase_42 AC 48 ms
5,180 KB
testcase_43 AC 65 ms
9,220 KB
testcase_44 AC 65 ms
9,208 KB
testcase_45 AC 65 ms
9,152 KB
testcase_46 AC 108 ms
8,000 KB
testcase_47 AC 133 ms
9,444 KB
testcase_48 AC 127 ms
9,364 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `ops::Sub`
 --> Main.rs:1:37
  |
1 | use std::{collections::*, io::Read, ops::Sub};
  |                                     ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: 1 warning emitted

ソースコード

diff # 

use std::{collections::*, io::Read, ops::Sub};

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
    }
}

fn binary_search<F: Fn(i64) -> bool>(ok_val: i64, ng_val: i64, check: F) -> i64 {
    let mut ok = ok_val;
    let mut ng = ng_val;
    while (ok - ng).abs() > 1 {
        let m = (ok + ng) / 2;
        if check(m) {
            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 = binary_search(0, (2e9) as i64, |m| {
        calc(&graph, n as usize, m as i32).is_some()
    }) as i32;

    println!("{} {}", k, calc(&graph, n as usize, k).unwrap());
}
0