結果

問題 No.2855 Move on Grid
ユーザー naut3naut3
提出日時 2024-08-25 14:57:38
言語 Rust
(1.77.0)
結果
AC  
実行時間 727 ms / 3,000 ms
コード長 9,693 bytes
コンパイル時間 13,405 ms
コンパイル使用メモリ 402,260 KB
実行使用メモリ 10,336 KB
最終ジャッジ日時 2024-08-25 14:58:17
合計ジャッジ時間 33,169 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
6,812 KB
testcase_01 AC 185 ms
6,944 KB
testcase_02 AC 119 ms
6,944 KB
testcase_03 AC 81 ms
6,944 KB
testcase_04 AC 55 ms
6,940 KB
testcase_05 AC 124 ms
6,940 KB
testcase_06 AC 123 ms
6,940 KB
testcase_07 AC 11 ms
6,940 KB
testcase_08 AC 94 ms
6,944 KB
testcase_09 AC 39 ms
6,940 KB
testcase_10 AC 468 ms
9,936 KB
testcase_11 AC 477 ms
10,112 KB
testcase_12 AC 514 ms
9,984 KB
testcase_13 AC 499 ms
9,940 KB
testcase_14 AC 514 ms
9,984 KB
testcase_15 AC 467 ms
9,984 KB
testcase_16 AC 474 ms
9,984 KB
testcase_17 AC 506 ms
9,984 KB
testcase_18 AC 496 ms
9,984 KB
testcase_19 AC 515 ms
9,936 KB
testcase_20 AC 624 ms
9,984 KB
testcase_21 AC 713 ms
10,208 KB
testcase_22 AC 625 ms
9,952 KB
testcase_23 AC 645 ms
9,944 KB
testcase_24 AC 602 ms
9,948 KB
testcase_25 AC 676 ms
10,204 KB
testcase_26 AC 580 ms
9,984 KB
testcase_27 AC 639 ms
10,332 KB
testcase_28 AC 613 ms
9,820 KB
testcase_29 AC 645 ms
9,984 KB
testcase_30 AC 666 ms
10,336 KB
testcase_31 AC 727 ms
10,328 KB
testcase_32 AC 673 ms
10,204 KB
testcase_33 AC 725 ms
10,200 KB
testcase_34 AC 701 ms
10,328 KB
testcase_35 AC 660 ms
10,332 KB
testcase_36 AC 633 ms
10,328 KB
testcase_37 AC 651 ms
10,328 KB
testcase_38 AC 718 ms
10,204 KB
testcase_39 AC 654 ms
10,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case, unused_must_use, unused_imports)]
use std::io::{self, prelude::*};

fn main() {
    let (stdin, stdout) = (io::read_to_string(io::stdin()).unwrap(), io::stdout());
    let (mut stdin, mut buffer) = (stdin.split_whitespace(), io::BufWriter::new(stdout.lock()));
    macro_rules! input {
        ($t: ty, $n: expr) => {
            (0..$n).map(|_| input!($t)).collect::<Vec<_>>()
        };
        ($t: ty) => {
            stdin.next().unwrap().parse::<$t>().unwrap()
        };
    }

    let N = input!(usize);
    let M = input!(usize);
    let K = input!(usize);
    let A = {
        let mut a = vec![];

        for _ in 0..N {
            let r = input!(u32, M);
            a.push(r);
        }

        a
    };

    let mut ok = 0;
    let mut ng = 1_000_000_001;

    while ng - ok > 1 {
        let m = (ok + ng) / 2;

        let mut graph = graph::DirectedGraph::<u32>::new(N * M + 1);
        let flatten = |y, x| y * M + x;

        graph.add_edge(N * M, 0, if A[0][0] < m { 1 } else { 0 });

        for y in 0..N {
            for x in 0..M {
                if y > 0 {
                    graph.add_edge(
                        flatten(y - 1, x),
                        flatten(y, x),
                        if A[y][x] < m { 1 } else { 0 },
                    );
                }

                if x > 0 {
                    graph.add_edge(
                        flatten(y, x - 1),
                        flatten(y, x),
                        if A[y][x] < m { 1 } else { 0 },
                    );
                }

                if x + 1 < M {
                    graph.add_edge(
                        flatten(y, x + 1),
                        flatten(y, x),
                        if A[y][x] < m { 1 } else { 0 },
                    );
                }

                if y + 1 < N {
                    graph.add_edge(
                        flatten(y + 1, x),
                        flatten(y, x),
                        if A[y][x] < m { 1 } else { 0 },
                    );
                }
            }
        }

        let dist = dijkstras_algorithm::dijkstras_algorithm(&graph, N * M);

        if dist[flatten(N - 1, M - 1)].0 <= K as u32 {
            ok = m;
        } else {
            ng = m;
        }
    }

    writeln!(buffer, "{}", ok);
}

pub mod extended_number {
    pub trait HasMaxValue {
        type S;
        const M: Self::S;
    }

    macro_rules! impl_primitives {
    ($($t: ty), *) => {
        $(
            impl HasMaxValue for $t {
                type S = $t;
                const M: Self::S = <$t>::MAX;
            }
        )*
    };
}

    impl_primitives!(usize, u128, u64, u32);

    /// the type of integer which regard `T::MAX` as infinity
    #[derive(Clone, Copy, PartialEq, PartialOrd, Eq, Ord, Hash, Default, Debug)]
    pub struct ExtendedNumber<N>(pub N);

    impl<N: HasMaxValue<S = N> + PartialEq + Eq> ExtendedNumber<N> {
        pub const INF: Self = Self(N::M);

        pub fn is_inf(&self) -> bool {
            self.0 == N::M
        }
    }

    impl<N: HasMaxValue<S = N> + PartialEq + Eq + Clone + std::ops::Add<Output = N>> std::ops::Add
        for ExtendedNumber<N>
    {
        type Output = Self;
        fn add(self, rhs: Self) -> Self::Output {
            if self.is_inf() || rhs.is_inf() {
                Self::INF
            } else {
                Self(self.0 + rhs.0)
            }
        }
    }

    impl<N: HasMaxValue<S = N> + PartialEq + Eq + Copy + std::ops::Add<Output = N>>
        std::ops::AddAssign for ExtendedNumber<N>
    {
        fn add_assign(&mut self, rhs: Self) {
            if self.is_inf() {
                return;
            }
            if rhs.is_inf() {
                *self = Self::INF;
                return;
            }
            *self = Self(self.0 + rhs.0)
        }
    }

    impl<N> From<N> for ExtendedNumber<N> {
        fn from(value: N) -> Self {
            Self(value)
        }
    }

    impl<N: HasMaxValue<S = N> + PartialEq + Eq + Clone + std::fmt::Display> std::fmt::Display
        for ExtendedNumber<N>
    {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(
                f,
                "{}",
                if self == &Self::INF {
                    "INF".to_string()
                } else {
                    format!("{}", self.0)
                }
            )
        }
    }
}

pub mod graph {
    pub type DirectedGraph<W> = Graph<DirectedEdge, AdjacencyList<W>, W>;
    pub type UndirectedGraph<W> = Graph<UndirectedEdge, AdjacencyList<W>, W>;
    pub type AdjGraph<O, W> = Graph<O, AdjacencyList<W>, W>;

    pub struct Graph<O, E: Expression<W>, W> {
        size: usize,
        pub expression: E,
        _marker: std::marker::PhantomData<(O, W)>,
    }

    impl<O: Orientation, E: Expression<W>, W: Copy> Graph<O, E, W> {
        /// return a graph with `size` vertices.
        pub fn new(size: usize) -> Self {
            Self {
                size,
                expression: E::new(size),
                _marker: std::marker::PhantomData::default(),
            }
        }

        pub fn from_edges(size: usize, edges: &[(usize, usize, W)]) -> Self {
            let mut graph = Self::new(size);

            for &(u, v, w) in edges {
                graph.add_edge(u, v, w);
            }

            graph
        }

        /// add an edge of weight `w` from `u` to `v`
        pub fn add_edge(&mut self, u: usize, v: usize, w: W) {
            if O::is_directed() {
                self.expression.add_edge(u, v, w);
            } else {
                self.expression.add_edge(u, v, w);
                self.expression.add_edge(v, u, w);
            }
        }

        /// enumerate edges from `u`
        pub fn adjacent(&self, u: usize) -> &[(u32, W)] {
            self.expression.adjacent(u)
        }

        /// return |V|
        pub fn size(&self) -> usize {
            self.size
        }
    }

    impl<O: Orientation, W: Copy> Graph<O, AdjacencyList<W>, W> {
        /// convert graph's memory layout to CRS
        pub fn to_crs(self) -> Graph<O, CRS<W>, W> {
            Graph {
                size: self.size,
                expression: self.expression.to_crs(),
                _marker: std::marker::PhantomData::default(),
            }
        }
    }

    /// the marker indicating whether edges of the graph are directed or undirected.
    pub trait Orientation {
        fn is_directed() -> bool;
    }

    pub struct DirectedEdge {}

    impl Orientation for DirectedEdge {
        fn is_directed() -> bool {
            true
        }
    }

    pub struct UndirectedEdge {}

    impl Orientation for UndirectedEdge {
        fn is_directed() -> bool {
            false
        }
    }

    pub trait Expression<W> {
        fn new(size: usize) -> Self;
        fn add_edge(&mut self, u: usize, v: usize, w: W);
        fn adjacent(&self, v: usize) -> &[(u32, W)]; // 本当は impl Iterator<Item = (usize, W)> にしたい
    }

    pub struct AdjacencyList<W> {
        adj: Vec<Vec<(u32, W)>>,
    }

    impl<W> AdjacencyList<W> {
        pub fn to_crs(mut self) -> CRS<W> {
            let mut adj = vec![];
            let mut ptr = vec![0];

            for i in 0..self.adj.len() {
                adj.append(&mut self.adj[i]);
                ptr.push(adj.len());
            }

            CRS { adj, ptr }
        }
    }

    impl<W: Copy> Expression<W> for AdjacencyList<W> {
        fn new(size: usize) -> Self {
            return Self {
                adj: vec![vec![]; size],
            };
        }

        fn add_edge(&mut self, u: usize, v: usize, w: W) {
            self.adj[u].push((v as u32, w));
        }

        fn adjacent(&self, v: usize) -> &[(u32, W)] {
            &self.adj[v]
        }
    }

    /// Compressed Row Storage
    pub struct CRS<W> {
        adj: Vec<(u32, W)>,
        ptr: Vec<usize>,
    }

    impl<W: Copy> Expression<W> for CRS<W> {
        fn new(_size: usize) -> Self {
            unreachable!()
        }

        fn add_edge(&mut self, _u: usize, _v: usize, _w: W) {
            unreachable!()
        }

        fn adjacent(&self, v: usize) -> &[(u32, W)] {
            &self.adj[self.ptr[v]..self.ptr[v + 1]]
        }
    }
}

pub mod dijkstras_algorithm {
    use crate::extended_number::{ExtendedNumber, HasMaxValue};
    use crate::graph::{AdjGraph, Orientation};
    use std::cmp::Reverse;

    pub fn dijkstras_algorithm<
        O: Orientation,
        W: Into<ExtendedNumber<W>>
            + Copy
            + HasMaxValue<S = W>
            + Default
            + Ord
            + std::ops::Add<Output = W>,
    >(
        graph: &AdjGraph<O, W>,
        src: usize,
    ) -> Vec<ExtendedNumber<W>> {
        let mut dist = vec![Into::<ExtendedNumber<W>>::into(W::M); graph.size()];
        dist[src] = Into::<ExtendedNumber<W>>::into(W::default());
        let mut seen = vec![false; graph.size()];

        let mut hq = std::collections::BinaryHeap::new();
        hq.push((Reverse(Into::<ExtendedNumber<W>>::into(W::default())), src));

        while let Some((_, u)) = hq.pop() {
            if seen[u] {
                continue;
            }

            seen[u] = true;

            for &(v, w) in graph.adjacent(u) {
                let v = v as usize;

                if !seen[v] {
                    let d = dist[u] + Into::<ExtendedNumber<W>>::into(w);

                    if d < dist[v] {
                        dist[v] = d;
                        hq.push((Reverse(d), v));
                    }
                }
            }
        }

        dist
    }
}
0