結果

問題 No.1473 おでぶなおばけさん
ユーザー mai
提出日時 2021-04-22 02:34:13
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 174 ms / 2,000 ms
コード長 2,998 bytes
コンパイル時間 13,056 ms
コンパイル使用メモリ 404,536 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-07-04 06:10:47
合計ジャッジ時間 17,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

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");
}
0