結果

問題 No.2855 Move on Grid
ユーザー naut3
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0