結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー RheoTommy
提出日時 2021-04-09 22:03:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 244 ms / 2,000 ms
コード長 10,045 bytes
コンパイル時間 12,054 ms
コンパイル使用メモリ 404,672 KB
実行使用メモリ 19,216 KB
最終ジャッジ日時 2024-06-25 05:31:45
合計ジャッジ時間 17,927 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

// # ファイル構成
// - use 宣言
// - lib モジュール
// - main 関数
// - basic モジュール
//
// 常に使うテンプレートライブラリは basic モジュール内にあります。
// 問題に応じて使うライブラリ lib モジュール内にコピペしています。
// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder
// Twitter はこちら → https://twitter.com/RheoTommy

use std::collections::*;
use std::io::{stdout, BufWriter, Write};

use crate::basic::*;
use crate::lib::*;

pub mod lib {
    /// UnionFind構造体
    /// UnionFind構造体
    pub struct UnionFindTree {
        /// 頂点`i`の親を格納する配列
        parents: Vec<usize>,
        /// 頂点`i`が親であるときのその木の頂点数
        sizes: Vec<usize>,
        /// 重み付きUnionFindを使う際の重みの格納配列
        weights: Vec<i64>,
        /// 頂点`i`が属する木がループを持っているかどうか
        has_loops: Vec<bool>,
        /// 連結成分数
        number_of_tree: usize,
    }

    impl UnionFindTree {
        /// UnionFind初期化
        /// 計算量はO(n)
        pub fn new(n: usize) -> Self {
            let parents = (0..n).collect();
            let sizes = vec![1; n];
            let weights = vec![0; n];
            let has_loops = vec![false; n];
            UnionFindTree {
                parents,
                sizes,
                weights,
                has_loops,
                number_of_tree: n,
            }
        }
        /// 親を再帰的に求め、途中の計算結果をもとに親の書き換えを行う関数
        /// 計算量はO(a(n)))
        pub fn root(&mut self, x: usize) -> usize {
            if self.parents[x] == x {
                x
            } else {
                let tmp = self.root(self.parents[x]);
                self.weights[x] += self.weights[self.parents[x]];
                self.parents[x] = tmp;
                tmp
            }
        }
        pub fn size(&mut self, x: usize) -> usize {
            let y = self.root(x);
            self.sizes[y]
        }
        pub fn has_loop(&mut self, x: usize) -> bool {
            let y = self.root(x);
            self.has_loops[y]
        }
        /// 2つの頂点が同じ木に属しているかの判定
        /// `self.root()`を呼び出すため、`&mut self`を引数に取る。そのため、命名に`is_`を使っていない
        /// 計算量はO(a(n))
        pub fn same(&mut self, x: usize, y: usize) -> bool {
            self.root(x) == self.root(y)
        }
        /// 重み付きUnionFindを考える際のUnite関数
        /// 計算量はO(a(n))
        pub fn unite_with_weight(&mut self, x: usize, y: usize, w: i64) {
            let root_x = self.root(x);
            let root_y = self.root(y);
            if self.same(x, y) {
                self.has_loops[root_x] = true;
                self.has_loops[root_y] = true;
            } else if self.sizes[root_x] >= self.sizes[root_y] {
                self.number_of_tree -= 1;
                self.parents[root_y] = root_x;
                self.has_loops[root_x] |= self.has_loops[root_y];
                self.sizes[root_x] += self.sizes[root_y];
                self.weights[root_y] = -w - self.weights[y] + self.weights[x];
            } else {
                self.number_of_tree -= 1;
                self.parents[root_x] = root_y;
                self.has_loops[root_y] |= self.has_loops[root_x];
                self.sizes[root_y] += self.sizes[root_x];
                self.weights[root_x] = w + self.weights[y] - self.weights[x];
            }
        }
        /// 重みを考慮しない際のUnite関数
        /// 重みとして0を与えているだけであり、計算量は同じくO(a(n))
        pub fn unite(&mut self, x: usize, y: usize) {
            self.unite_with_weight(x, y, 0);
        }
        /// 重み付きUnionFindにおいて、2つの頂点の距離を返す関数
        /// 2つの頂点が同じ木に属していない場合は`None`を返す
        pub fn diff(&mut self, x: usize, y: usize) -> Option<i64> {
            if self.same(x, y) {
                Some(self.weights[x] - self.weights[y])
            } else {
                None
            }
        }
        pub fn is_parent(&self, x: usize) -> bool {
            self.parents[x] == x
        }
        pub fn number_of_tree(&self) -> usize {
            self.number_of_tree
        }
    }

    /// 関数Fを適用すると[false..false,true..true]の形にできるような配列において、初めてtrueになるIndexを返す
    /// O(log n)
    pub trait BinarySearch<T> {
        /// 存在しなかった場合は配列の長さを返す
        fn lower_bound(&self, f: impl FnMut(&T) -> bool) -> usize;
        /// 存在しなかった場合はNoneを返す
        fn lower_bound_safe(&self, f: impl FnMut(&T) -> bool) -> Option<usize>;
    }

    impl<T> BinarySearch<T> for [T] {
        /// 任意のランダムアクセス可能なスライスに対して実行可能な実装
        fn lower_bound(&self, mut f: impl FnMut(&T) -> bool) -> usize {
            let mut left: isize = -1;
            let mut right = self.len() as isize;
            while right - left > 1 {
                let mid = (left + right) / 2;
                if f(&self[mid as usize]) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            right as usize
        }
        fn lower_bound_safe(&self, f: impl FnMut(&T) -> bool) -> Option<usize> {
            let i = self.lower_bound(f);
            if i == self.len() {
                None
            } else {
                Some(i)
            }
        }
    }

    pub fn lower_bound<
        T: Copy + std::ops::Add<Output = T> + std::ops::Div<Output = T> + From<i32>,
    >(
        mut l: T,
        mut r: T,
        mut f: impl FnMut(T) -> bool,
        mut g: impl FnMut(T, T) -> bool,
    ) -> Option<T> {
        if !f(r) {
            return None;
        }
        while g(l, r) {
            let mid = (l + r) / T::from(2i32);
            if f(mid) {
                r = mid;
            } else {
                l = mid;
            }
        }
        Some(r)
    }
}

fn main() {
    let mut io = IO::new();
    let n = io.next_usize();
    let m = io.next_usize();
    let mut vertexes = vec![vec![]; n];
    let mut edges = vec![];
    for _ in 0..m {
        let s = io.next_usize() - 1;
        let t = io.next_usize() - 1;
        let d = io.next_int();
        edges.push((s, t, d));
        vertexes[s].push((t, d));
        vertexes[t].push((s, d));
    }

    let judge = |w: i64| {
        let mut uf = UnionFindTree::new(n);
        for &(s, t, d) in &edges {
            if w <= d {
                uf.unite(s, t);
            }
        }
        uf.same(0, n - 1)
    };

    let max = lower_bound(2 * 1000000000, 0i64, judge, |a, b| (a - b).abs() > 1).unwrap();
    io.print(max);

    let mut dp = vec![U_INF; n];
    dp[0] = 0;
    let mut queue = VecDeque::new();
    queue.push_back(0);
    while let Some(now) = queue.pop_front() {
        for &(t, d) in &vertexes[now] {
            if d >= max && dp[t] > dp[now] + 1 {
                dp[t] = dp[now] + 1;
                queue.push_back(t);
            }
        }
    }
    io.print(" ");
    io.println(dp[n - 1]);
}

pub mod basic {
    pub const U_INF: u64 = (1 << 60) + (1 << 30);
    pub const I_INF: i64 = (1 << 60) + (1 << 30);

    pub struct IO {
        iter: std::str::SplitAsciiWhitespace<'static>,
        buf: std::io::BufWriter<std::io::StdoutLock<'static>>,
    }

    impl IO {
        pub fn new() -> Self {
            use std::io::*;
            let mut input = String::new();
            std::io::stdin().read_to_string(&mut input).unwrap();
            let input = Box::leak(input.into_boxed_str());
            let out = Box::new(stdout());
            IO {
                iter: input.split_ascii_whitespace(),
                buf: BufWriter::new(Box::leak(out).lock()),
            }
        }

        pub fn next_str(&mut self) -> &str {
            self.iter.next().unwrap()
        }

        pub fn next<T: std::str::FromStr>(&mut self) -> T
        where
            <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            self.iter.next().unwrap().parse().unwrap()
        }

        pub fn next_usize(&mut self) -> usize {
            self.next()
        }

        pub fn next_uint(&mut self) -> u64 {
            self.next()
        }

        pub fn next_int(&mut self) -> i64 {
            self.next()
        }

        pub fn next_float(&mut self) -> f64 {
            self.next()
        }

        pub fn next_chars(&mut self) -> std::str::Chars {
            self.next_str().chars()
        }

        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T>
        where
            <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            (0..n).map(|_| self.next()).collect::<Vec<_>>()
        }

        pub fn print<T: std::fmt::Display>(&mut self, t: T) {
            use std::io::Write;
            write!(self.buf, "{}", t).unwrap();
        }

        pub fn println<T: std::fmt::Display>(&mut self, t: T) {
            self.print(t);
            self.print("\n");
        }

        pub fn print_iter<T: std::fmt::Display, I: Iterator<Item = T>>(
            &mut self,
            mut iter: I,
            sep: &str,
        ) {
            if let Some(v) = iter.next() {
                self.print(v);
                for vi in iter {
                    self.print(sep);
                    self.print(vi);
                }
            }
            self.print("\n");
        }

        pub fn flush(&mut self) {
            use std::io::Write;
            self.buf.flush().unwrap();
        }
    }
}
0