結果

問題 No.2786 RMQ on Grid Path
ユーザー maguroflymagurofly
提出日時 2024-06-14 22:20:42
言語 Rust
(1.77.0)
結果
AC  
実行時間 689 ms / 6,000 ms
コード長 2,395 bytes
コンパイル時間 12,825 ms
コンパイル使用メモリ 380,172 KB
実行使用メモリ 63,424 KB
最終ジャッジ日時 2024-06-14 22:21:18
合計ジャッジ時間 28,949 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 0 ms
6,820 KB
testcase_02 AC 2 ms
6,812 KB
testcase_03 AC 3 ms
6,816 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 3 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 3 ms
6,944 KB
testcase_12 AC 594 ms
63,128 KB
testcase_13 AC 617 ms
62,840 KB
testcase_14 AC 623 ms
62,088 KB
testcase_15 AC 689 ms
63,248 KB
testcase_16 AC 623 ms
62,732 KB
testcase_17 AC 645 ms
63,424 KB
testcase_18 AC 605 ms
62,172 KB
testcase_19 AC 637 ms
62,356 KB
testcase_20 AC 589 ms
62,856 KB
testcase_21 AC 631 ms
62,472 KB
testcase_22 AC 480 ms
54,396 KB
testcase_23 AC 481 ms
52,348 KB
testcase_24 AC 526 ms
59,044 KB
testcase_25 AC 527 ms
59,040 KB
testcase_26 AC 529 ms
59,048 KB
testcase_27 AC 271 ms
26,112 KB
testcase_28 AC 318 ms
25,032 KB
testcase_29 AC 490 ms
53,396 KB
testcase_30 AC 300 ms
23,844 KB
testcase_31 AC 35 ms
5,504 KB
testcase_32 AC 472 ms
59,108 KB
testcase_33 AC 306 ms
18,336 KB
testcase_34 AC 494 ms
58,972 KB
testcase_35 AC 493 ms
58,880 KB
testcase_36 AC 485 ms
59,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashSet;

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        h: usize, w: usize,
        a: [[usize; w]; h],
        q: usize,
        queries: [(Usize1, Usize1, Usize1, Usize1); q],
    }

    let mut ans = vec![0; q];
    let mut sets = vec![HashSet::new(); h * w];
    let mut uf = UnionFind::new(h * w);

    for j in 0 .. q {
        let (si, sj, ti, tj) = queries[j];
        sets[si * w + sj].insert(j);
        sets[ti * w + tj].insert(j);
    }

    let mut edges = vec![];
    for i in 0 .. h {
        for j in 0 .. w - 1 {
            edges.push((a[i][j].max(a[i][j + 1]), i * w + j, i * w + j + 1));
        }
    }
    for i in 0 .. h - 1 {
        for j in 0 .. w {
            edges.push((a[i][j].max(a[i + 1][j]), i * w + j, (i + 1) * w + j));
        }
    }
    edges.sort();

    for (cost, u, v) in edges {
        let r = uf.leader(u);
        let s = uf.leader(v);
        if r != s {
            let mut x = std::mem::take(&mut sets[r]);
            let mut y = std::mem::take(&mut sets[s]);
            if x.len() < y.len() {
                std::mem::swap(&mut x, &mut y);
            }
            for j in y {
                if x.contains(&j) {
                    x.remove(&j);
                    ans[j] = cost;
                } else {
                    x.insert(j);
                }
            }
            uf.merge(r, s);
            sets[uf.leader(r)] = x;
        }
    }

    for j in 0 .. q {
        println!("{}", ans[j]);
    }
}

pub struct UnionFind(Vec<isize>, usize);
impl UnionFind {
  pub fn new(n: usize) -> Self { Self(vec![-1; n], n) }
  pub fn leader(&mut self, mut i: usize) -> usize { let k = self.0[i]; if k >= 0 { let j = self.leader(k as usize); self.0[i] = j as isize; i = j; }; i }
  pub fn merge(&mut self, mut i: usize, mut j: usize) -> bool { i = self.leader(i); j = self.leader(j); i != j && { if self.0[i] > self.0[j] { let k = i; i = j; j = k; }; self.0[i] += self.0[j]; self.0[j] = i as isize; true } }
  pub fn same(&mut self, i: usize, j: usize) -> bool { self.leader(i) == self.leader(j) }
  pub fn size(&mut self, mut i: usize) -> usize { i = self.leader(i); -self.0[i] as usize }
  pub fn groups(&mut self) -> Vec<Vec<usize>> { let mut s = vec![vec![]; self.1]; for i in 0 .. self.1 { s[self.leader(i)].push(i) }; s.into_iter().filter(|g| g.len() > 0 ).collect::<Vec<_>>() }
}
0