Submission #16768460


Source Code Expand

Copy
use proconio::input;

fn main() {
    input! {
        h: usize,
        w: usize,
        a: [[i64; w]; h],
    };
    let mut e_i = vec![vec![]; w * h];
    let mut e_o = vec![vec![]; w * h];
    for r in 0..h {
        for c in 0..w {
            let v = a[r][c];
            let dir = vec![(-1, 0), (0, -1), (0, 1), (1, 0)];
            for (d_r, d_c) in dir.iter() {
                let (r_n, c_n) = (r as i64 + d_r, c as i64 + d_c);
                if (0..h as i64).contains(&r_n) && (0..w as i64).contains(&c_n) {
                    let (r_n, c_n) = (r_n as usize, c_n as usize);
                    let v_n = a[r_n][c_n];
                    if v_n < v {
                        e_i[r * w + c].push(r_n * w + c_n);
                    } else if v_n > v {
                        e_o[r * w + c].push(r_n * w + c_n);
                    }
                }
            }
        }
    }
    let mut b = vec![];
    for r in 0..h {
        for c in 0..w {
            b.push((a[r][c], r, c));
        }
    }
    b.sort_by_key(|(v, _, _)| -v);
    let mut done = vec![false; h * w];
    let mut d = vec![0; h * w];
    for &(_, br, bc) in b.iter() {
        if done[br * w + bc] {
            continue;
        }
        let mut q = std::collections::VecDeque::new();
        q.push_back(br * w + bc);
        while let Some(p) = q.pop_front() {
            done[p] = true;
            d[p] += 1;
            d[p] %= 1_000_000_007;
            for &p_i in e_i[p].iter() {
                d[p_i] += d[p];
                d[p_i] %= 1_000_000_007;
                for j in 0..e_o[p_i].len() {
                    if e_o[p_i][j] == p {
                        e_o[p_i].remove(j);
                        break;
                    }
                }
                if e_o[p_i].is_empty() {
                    q.push_back(p_i);
                }
            }
        }
    }
    let mut ans = 0;
    for &d_i in d.iter() {
        ans += d_i;
        ans %= 1_000_000_007;
    }
    println!("{}", ans);
}

Submission Info

Submission Time
Task D - 経路
User bouzuya
Language Rust (1.42.0)
Score 100
Code Size 2011 Byte
Status
Exec Time 690 ms
Memory 160328 KB

Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample01.txt, sample02.txt
All 100 / 100 00.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, sample01.txt, sample02.txt, sample01.txt, sample02.txt
Case Name Status Exec Time Memory
00.txt 467 ms 158548 KB
01.txt 319 ms 157496 KB
02.txt 355 ms 141868 KB
03.txt 1 ms 2068 KB
04.txt 1 ms 2044 KB
05.txt 2 ms 2084 KB
06.txt 2 ms 2228 KB
07.txt 1 ms 2308 KB
08.txt 2 ms 2164 KB
09.txt 2 ms 2052 KB
10.txt 4 ms 2532 KB
11.txt 682 ms 160224 KB
12.txt 684 ms 160328 KB
13.txt 684 ms 160284 KB
14.txt 682 ms 160312 KB
15.txt 565 ms 159800 KB
16.txt 690 ms 160312 KB
17.txt 689 ms 160208 KB
18.txt 304 ms 124904 KB
19.txt 127 ms 86988 KB
sample01.txt 1 ms 1908 KB
sample02.txt 1 ms 2040 KB