結果

問題 No.20 砂漠のオアシス
ユーザー snteasntea
提出日時 2018-10-20 01:42:40
言語 Rust
(1.72.1)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 11,400 bytes
コンパイル時間 1,449 ms
コンパイル使用メモリ 171,516 KB
実行使用メモリ 6,708 KB
最終ジャッジ日時 2023-08-12 04:02:22
合計ジャッジ時間 2,390 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 16 ms
5,824 KB
testcase_06 AC 18 ms
6,700 KB
testcase_07 AC 18 ms
6,628 KB
testcase_08 AC 18 ms
6,708 KB
testcase_09 AC 18 ms
6,684 KB
testcase_10 AC 1 ms
4,384 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 4 ms
4,380 KB
testcase_17 AC 3 ms
4,384 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 4 ms
4,380 KB
testcase_20 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `from`
   --> 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
   --> 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: associated function `add_uedge` is never used
   --> Main.rs:155:8
    |
155 |     fn add_uedge(&mut self, from: usize, to_: usize, cost_: Cost) {
    |        ^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: associated function `vizualize` is never used
   --> Main.rs:322:8
    |
322 |     fn vizualize(&self, name: &str) {
    |        ^^^^^^^^^

warning: associated function `viz_with_cost` is never used
   --> Main.rs:352:8
    |
352 |     fn viz_with_cost(&self, name: &str) {
    |        ^^^^^^^^^^^^^

warning: unused `Result` that must be used
   --> Main.rs:332:17
    |
332 |                 writeln!(&mut out, "    {}[];", p);
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: this `Result` may be an `Err` variant, which should be handled
    = note: `#[warn(unused_must_use)]` on by default
    = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: unused `Result` that must be used
   --> Main.rs:336:21
    |
336 |      

ソースコード

diff #

// 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>, ());
    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>, ()) {
        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, ())
    }

    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, )
}
0