結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:57:38 |
言語 | Rust (1.83.0 + proconio) |
結果 |
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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#![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::Addfor 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::Displayfor 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 CRSpub 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 Storagepub 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}}