結果
| 問題 |
No.20 砂漠のオアシス
|
| コンテスト | |
| ユーザー |
 sntea
|
| 提出日時 | 2018-10-20 01:37:32 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 20 ms / 5,000 ms |
| コード長 | 11,411 bytes |
| コンパイル時間 | 13,306 ms |
| コンパイル使用メモリ | 386,900 KB |
| 実行使用メモリ | 6,856 KB |
| 最終ジャッジ日時 | 2024-11-19 00:38:18 |
| 合計ジャッジ時間 | 14,474 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 |
コンパイルメッセージ
warning: unused variable: `from`
--> src/main.rs:306:39
|
306 | fn get_shortest_path_graph(&self, from: usize, dist: &Vec<Self::Cost>) -> AdjList<Self::Cost> {
| ^^^^ help: if this is intentional, prefix it with an underscore: `_from`
|
= note: `#[warn(unused_variables)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:9:13
|
9 | let mut s = {
| ----^
| |
| help: remove this `mut`
...
390 | / input! {
391 | | n: usize,
392 | | v: i32,
393 | | ox: usize,
394 | | oy: usize,
395 | | l: [[i32; n]; n],
396 | | }
| |_____- in this macro invocation
|
= note: `#[warn(unused_mut)]` on by default
= note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: method `add_uedge` is never used
--> src/main.rs:155:8
|
141 | impl<Cost: Clone> AdjList<Cost> {
| ------------------------------- method in this implementation
...
155 | fn add_uedge(&mut self, from: usize, to_: usize, cost_: Cost) {
| ^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: method `vizualize` is never used
--> src/main.rs:322:8
|
321 | impl<Cost: Clone> AdjList<Cost> {
| ------------------------------- method in this implementation
322 | fn vizualize(&self, name: &str) {
| ^^^^^^^^^
warning: method `viz_with_cost` is never used
--> src/main.rs:352:8
|
351 | impl<Cost: Clone + std::fmt::Display> AdjList<Cost> {
| --------------------------------------------------- method in this implementation
352 | fn viz_with_cost(&self, name: &str) {
| ^^^^^^^^^^^^^
warning: unused `Result` that must be used
--> src/main.rs:332:17
|
332 | writeln!(&mut out, " {}[];", p);
| ^^^^^^^^^^^^^^^^^^^^^
ソースコード
// from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
#[allow(unused_macros)]
macro_rules! debug {
($x: expr) => {
println!("{}: {:?}", stringify!($x), $x)
};
}
// macro_rules! debug { ($x: expr) => () }
#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
T: Iterator,
T::Item: std::fmt::Display,
{
let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
res.pop();
res
}
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::mem::swap;
use std::clone::Clone;
use std::cmp::Ordering;
#[derive(Clone, Debug, Hash, Eq, PartialEq)]
struct Edge<Cost>
where
Cost: std::clone::Clone,
{
to: usize,
cost: Cost,
}
impl<Cost> Ord for Edge<Cost>
where
Cost: Ord + std::clone::Clone,
{
fn cmp(&self, other: &Edge<Cost>) -> Ordering {
(self.cost).cmp(&(other.cost)).reverse()
}
}
impl<Cost> PartialOrd for Edge<Cost>
where
Cost: std::clone::Clone,
Edge<Cost>: Ord,
{
fn partial_cmp(&self, other: &Edge<Cost>) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
trait Graph
where
Self::Cost: Clone,
{
type Cost;
fn len(&self) -> usize;
fn get<'a>(&'a self, p: usize) -> std::slice::Iter<'a, Edge<Self::Cost>>;
fn get_order(&self) -> Vec<usize>;
}
#[derive(Clone, Debug, Hash)]
struct AdjList<Cost: Clone> {
adj: Vec<Vec<Edge<Cost>>>,
}
impl<Cost: Clone> std::ops::Index<usize> for AdjList<Cost> {
type Output = Vec<Edge<Cost>>;
fn index(&self, i: usize) -> &Vec<Edge<Cost>> {
&self.adj[i]
}
}
impl<Cost: Clone> std::ops::IndexMut<usize> for AdjList<Cost> {
fn index_mut<'a>(&'a mut self, i: usize) -> &'a mut Vec<Edge<Cost>> {
&mut self.adj[i]
}
}
impl<Cost: Clone> AdjList<Cost> {
fn new(n: usize) -> AdjList<Cost> {
AdjList {
adj: vec![vec![]; n],
}
}
fn add_edge(&mut self, from: usize, to_: usize, cost_: Cost) {
self.adj[from].push(Edge {
to: to_,
cost: cost_,
});
}
fn add_uedge(&mut self, from: usize, to_: usize, cost_: Cost) {
self.add_edge(from, to_, cost_.clone());
self.add_edge(to_, from, cost_);
}
}
impl<Cost> Graph for AdjList<Cost>
where
Cost: Clone,
{
type Cost = Cost;
fn len(&self) -> usize {
self.adj.len()
}
fn get<'a>(&'a self, p: usize) -> std::slice::Iter<'a, Edge<Cost>> {
self.adj[p].iter()
}
fn get_order(&self) -> Vec<usize> {
let mut res = Vec::with_capacity(self.len());
let mut deg = vec![0; self.len()];
let mut used = vec![false; self.len()];
for from in 0..self.len() {
for e in self.get(from) {
deg[e.to] += 1;
}
}
for s in 0..self.len() {
if deg[s] != 0 || used[s] {
continue;
}
let mut stack = Vec::new();
used[s] = true;
stack.push(s);
while let Some(p) = stack.pop() {
used[p] = true;
res.push(p);
for e in self.get(p) {
deg[e.to] -= 1;
if deg[e.to] == 0 {
stack.push(e.to);
}
}
}
}
// debug!(deg);
res
}
}
// --------------------
trait Zero {
fn zero() -> Self;
}
impl Zero for i64 {
fn zero() -> i64 {
0
}
}
impl Zero for i32 {
fn zero() -> i32 {
0
}
}
trait Max {
fn max_value() -> Self;
}
impl Max for i64 {
fn max_value() -> i64 {
std::i64::MAX
}
}
impl Max for i32 {
fn max_value() -> i32 {
std::i32::MAX
}
}
trait GraphHavingOrderedCost: Graph
where
Self::Cost: Ord + Add<Self::Cost, Output = Self::Cost> + Zero + Max + Copy,
{
fn get_shortest_path(&self, from: usize) -> (Vec<Self::Cost>, Vec<usize>);
fn bellmanford(&self, from: usize) -> (Vec<Self::Cost>, Vec<bool>);
fn get_shortest_path_graph(&self, from: usize, dist: &Vec<Self::Cost>) -> AdjList<Self::Cost>;
}
use std::ops::Add;
impl<T> GraphHavingOrderedCost for T
where
T: Graph,
T::Cost: Ord + Add<T::Cost, Output = T::Cost> + Zero + Max + Copy,
Edge<T::Cost>: Ord,
{
fn get_shortest_path(&self, from: usize) -> (Vec<Self::Cost>, Vec<usize>) {
let n = self.len();
let mut dist = vec![Self::Cost::max_value(); n];
let mut pre = vec![n as usize; n];
let mut heap = std::collections::BinaryHeap::new();
heap.push(Edge {
to: from,
cost: Self::Cost::zero(),
});
dist[from] = Self::Cost::zero();
while let Some(p) = heap.pop() {
for e in self.get(p.to) {
if p.cost + e.cost >= dist[e.to] {
continue;
}
heap.push(Edge {
to: e.to,
cost: p.cost + e.cost,
});
dist[e.to] = p.cost + e.cost;
pre[e.to] = p.to;
}
}
(dist, pre)
}
fn bellmanford(&self, from: usize) -> (Vec<Self::Cost>, Vec<bool>) {
let n = self.len();
let mut dist = vec![Self::Cost::max_value(); n];
let mut updated = vec![true; n];
dist[from] = Self::Cost::zero();
for _ in 0..n + 1 {
updated = vec![false; n];
for from in 0..n {
if dist[from] == Self::Cost::max_value() {
continue;
}
for e in self.get(from) {
if dist[e.to] > dist[from] + e.cost {
dist[e.to] = dist[from] + e.cost;
updated[e.to] = true;
}
}
}
}
(dist, updated)
}
fn get_shortest_path_graph(&self, from: usize, dist: &Vec<Self::Cost>) -> AdjList<Self::Cost> {
let n = self.len();
let mut res = AdjList::new(n);
for from in 0..n {
for e in self.get(from) {
if dist[from] + e.cost == dist[e.to] {
res.add_edge(from, e.to, e.cost);
}
}
}
res
}
}
impl<Cost: Clone> AdjList<Cost> {
fn vizualize(&self, name: &str) {
let path = std::path::Path::new("tmp.dot");
{
use std::io::{BufWriter, Write};
let file = std::fs::File::create(path).unwrap();
let mut out = BufWriter::new(file);
let n = self.len();
writeln!(&mut out, "digraph graph_name {{").unwrap();
for p in 0..n {
writeln!(&mut out, " {}[];", p);
}
for p in 0..n {
for e in &self[p] {
writeln!(&mut out, " {} -> {}", p, e.to);
}
}
writeln!(&mut out, "}}");
}
let mut cmd = std::process::Command::new("dot");
cmd.arg("-T");
cmd.arg("png");
cmd.arg("tmp.dot");
cmd.arg("-o");
cmd.arg(name);
cmd.status().expect("failed to execute dot");
}
}
impl<Cost: Clone + std::fmt::Display> AdjList<Cost> {
fn viz_with_cost(&self, name: &str) {
let path = std::path::Path::new("tmp.dot");
{
use std::io::{BufWriter, Write};
let file = std::fs::File::create(path).unwrap();
let mut out = BufWriter::new(file);
let n = self.len();
writeln!(&mut out, "digraph graph_name {{").unwrap();
for p in 0..n {
writeln!(&mut out, " {}[];", p);
}
for p in 0..n {
for e in &self[p] {
writeln!(&mut out, " {} -> {} [label={}]", p, e.to, e.cost);
}
}
writeln!(&mut out, "}}");
}
let mut cmd = std::process::Command::new("dot");
cmd.arg("-T");
cmd.arg("png");
cmd.arg("tmp.dot");
cmd.arg("-o");
cmd.arg(name);
cmd.status().expect("failed to execute dot");
}
}
fn main() {
use std::io::Write;
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
#[allow(unused_macros)]
macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
#[allow(unused_macros)]
macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }
input! {
n: usize,
v: i32,
ox: usize,
oy: usize,
l: [[i32; n]; n],
}
// let v = v - l[0][0];
let dx = [0, -1, 0, 1];
let dy = [-1, 0, 1, 0];
let mut g = AdjList::new(n * n);
let get_idx = |i, j| i * n + j;
for i in 0..n {
for j in 0..n {
for k in 0..4 {
let ni = i as i64 + dx[k];
let nj = j as i64 + dy[k];
if 0 <= ni && ni < n as i64 && 0 <= nj && nj < n as i64 {
let ni = ni as usize;
let nj = nj as usize;
g.add_edge(get_idx(i, j), get_idx(ni, nj), l[ni][nj]);
}
}
}
}
let mut ans = false;
let (dist0, _) = g.get_shortest_path(get_idx(0, 0));
// debug!(v - dist0[get_idx(n - 1, n - 1)]);
if v - dist0[get_idx(n - 1, n - 1)] > 0 {
ans = true;
}
if ox != 0 {
let ox = ox - 1;
let oy = oy - 1;
let (dist1, _) = g.get_shortest_path(get_idx(oy, ox));
// debug!((v - dist0[get_idx(ox, oy)]) * 2 - dist1[get_idx(n - 1, n - 1)]);
if (v - dist0[get_idx(oy, ox)]) * 2 - dist1[get_idx(n - 1, n - 1)] > 0 {
ans = true;
}
}
if ans {
printfln!("YES");
} else {
printfln!("NO");
}
// fn dfs(x: usize, y: usize, )
}