#695508 (Rust) No.1668 Grayscale

• 問題: No.1668 Grayscale
• ユーザー: akakimidori
• 提出日時: 2021-09-03 22:01:31
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 5,930 bytes
• コンパイル時間: 12,291 ms
• コンパイル使用メモリ: 398,028 KB
• 実行使用メモリ: 196,224 KB
• 最終ジャッジ日時: 2024-12-15 13:18:19
• 合計ジャッジ時間: 15,173 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 7 WA * 15

コンパイルメッセージ

warning: unused import: `std::io::Write`
   --> src/main.rs:145:5
    |
145 | use std::io::Write;
    |     ^^^^^^^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `n`
   --> src/main.rs:156:9
    |
156 |         n: usize,
    |         ^
    |
help: `n` is captured in macro and introduced a unused variable
   --> src/main.rs:118:13
    |
118 |           let $var = read_value!($iter, $t);
    |               ^^^^
...
153 | /     input! {
154 | |         h: usize,
155 | |         w: usize,
156 | |         n: usize,
157 | |         c: [[usize; w]; h],
158 | |     }
    | |_____- in this macro invocation
    = note: `#[warn(unused_variables)]` on by default
    = note: this warning originates in the macro `input_inner` which comes from the expansion of the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: type alias `Map` is never used
   --> src/main.rs:148:6
    |
148 | type Map<K, V> = BTreeMap<K, V>;
    |      ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
   --> src/main.rs:149:6
    |
149 | type Set<T> = BTreeSet<T>;
    |      ^^^

warning: type alias `Deque` is never used
   --> src/main.rs:150:6
    |
150 | type Deque<T> = VecDeque<T>;
    |      ^^^^^

ソースコード

// ---------- begin SCC ----------
pub struct SCC {
    size: usize,
    edge: Vec<(u32, u32)>,
}

impl SCC {
    pub fn new(size: usize) -> Self {
        assert!(size <= 10usize.pow(8));
        SCC { size, edge: vec![] }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        assert!(a < self.size && b < self.size);
        self.edge.push((a as u32, b as u32));
    }
    pub fn build(&self) -> (usize, Vec<usize>) {
        let size = self.size;
        let mut start = vec![0u32; size + 1];
        self.edge.iter().for_each(|e| start[e.0 as usize + 1] += 1);
        for i in 1..=size {
            start[i] += start[i - 1];
        }
        let mut buf = vec![0u32; self.edge.len()];
        for &(a, b) in self.edge.iter() {
            let po = &mut start[a as usize];
            buf[*po as usize] = b;
            *po += 1;
        }
        let mut s = 0usize;
        let neighbor = start[..size].iter().map(|t| {
            let t = *t as usize;
            let it = buf[s..t].iter().map(|p| *p as usize);
            s = t;
            it
        }).collect::<Vec<_>>();
        struct Graph<I> {
            neighbor: Vec<I>,
            ord: Vec<usize>,
            assigned: Vec<bool>,
            stack_s: Vec<usize>,
            stack_p: Vec<usize>,
            cnt: usize,
            id: usize,
            res: Vec<usize>,
        }
        impl<I: Iterator<Item = usize>> Graph<I> {
            fn dfs(&mut self, v: usize) {
                self.ord[v] = self.cnt;
                self.cnt += 1;
                self.stack_s.push(v);
                self.stack_p.push(v);
                while let Some(u) = self.neighbor[v].next() {
                    if self.ord[u] == !0 {
                        self.dfs(u);
                    } else if !self.assigned[u] {
                        while self.ord[*self.stack_p.last().unwrap()] > self.ord[u] {
                            self.stack_p.pop();
                        }
                    }
                }
                if *self.stack_p.last().unwrap() == v {
                    while let Some(u) = self.stack_s.pop() {
                        self.res[u] = self.id;
                        self.assigned[u] = true;
                        if u == v {
                            break;
                        }
                    }
                    self.stack_p.pop();
                    self.id += 1;
                }
            }
        }
        let mut g = Graph {
            neighbor: neighbor,
            ord: vec![!0; size],
            assigned: vec![false; size],
            stack_s: vec![],
            stack_p: vec![],
            id: 0,
            cnt: 0,
            res: vec![0; size],
        };
        for i in 0..size {
            if g.ord[i] == !0 {
                g.dfs(i);
            }
        }
        let Graph { mut res, id, .. } = g;
        res.iter_mut().for_each(|v| *v = id - 1 - *v);
        (id, res)
    }
}
// ---------- end SCC ----------
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let 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)*}
    };
}

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)*}
    };
}

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, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn run() {
    input! {
        h: usize,
        w: usize,
        n: usize,
        c: [[usize; w]; h],
    }
    let pos = |x: usize, y: usize| -> usize {
        assert!(x < h && y < w);
        x * w + y
    };
    let mut edge = vec![];
    for (i, c) in c.windows(2).enumerate() {
        for (j, (x, y)) in c[0].iter().zip(&c[1]).enumerate() {
            if *x >= *y {
                edge.push((pos(i, j), pos(i + 1, j)));
            }
            if *x <= *y {
                edge.push((pos(i + 1, j), pos(i, j)));
            }
        }
    }
    for (i, c) in c.iter().enumerate() {
        for (j, c) in c.windows(2).enumerate() {
            if c[0] >= c[1] {
                edge.push((pos(i, j), pos(i, j + 1)));
            }
            if c[0] <= c[1] {
                edge.push((pos(i, j + 1), pos(i, j)));
            }
        }
    }
    let mut scc = SCC::new(h * w);
    for &(a, b) in edge.iter() {
        scc.add_edge(a, b);
    }
    let (len, id) = scc.build();
    let mut g = vec![vec![]; len];
    for (a, b) in edge {
        let a = id[a];
        let b = id[b];
        if a < b {
            g[a].push(b);
        }
    }
    let mut dp = vec![1; len];
    for (i, g) in g.iter().enumerate().rev() {
        dp[i] = g.iter().map(|p| dp[*p] + 1).max().unwrap_or(1);
    }
    println!("{}", *dp.iter().max().unwrap());
}

fn main() {
    run();
}