結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー magurofly
提出日時 2024-06-14 22:20:42
言語 Rust
(1.83.0 + proconio)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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