結果

問題 No.1479 Matrix Eraser
ユーザー 37kt37kt
提出日時 2024-12-02 12:11:48
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 479 ms / 3,000 ms
コード長 4,473 bytes
コンパイル時間 14,414 ms
コンパイル使用メモリ 378,156 KB
実行使用メモリ 83,660 KB
最終ジャッジ日時 2024-12-02 12:12:15
合計ジャッジ時間 23,978 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
36,972 KB
testcase_01 AC 23 ms
37,172 KB
testcase_02 AC 24 ms
37,016 KB
testcase_03 AC 23 ms
37,008 KB
testcase_04 AC 22 ms
37,076 KB
testcase_05 AC 24 ms
37,072 KB
testcase_06 AC 23 ms
37,036 KB
testcase_07 AC 63 ms
42,400 KB
testcase_08 AC 101 ms
45,956 KB
testcase_09 AC 199 ms
55,416 KB
testcase_10 AC 386 ms
68,968 KB
testcase_11 AC 231 ms
58,220 KB
testcase_12 AC 72 ms
43,892 KB
testcase_13 AC 92 ms
46,036 KB
testcase_14 AC 77 ms
44,068 KB
testcase_15 AC 35 ms
38,616 KB
testcase_16 AC 88 ms
45,016 KB
testcase_17 AC 448 ms
74,424 KB
testcase_18 AC 446 ms
74,516 KB
testcase_19 AC 433 ms
74,572 KB
testcase_20 AC 451 ms
74,668 KB
testcase_21 AC 468 ms
74,496 KB
testcase_22 AC 472 ms
74,468 KB
testcase_23 AC 473 ms
74,428 KB
testcase_24 AC 479 ms
74,552 KB
testcase_25 AC 468 ms
74,480 KB
testcase_26 AC 466 ms
74,676 KB
testcase_27 AC 140 ms
51,928 KB
testcase_28 AC 138 ms
51,780 KB
testcase_29 AC 140 ms
51,808 KB
testcase_30 AC 139 ms
51,484 KB
testcase_31 AC 142 ms
51,980 KB
testcase_32 AC 78 ms
54,880 KB
testcase_33 AC 79 ms
55,260 KB
testcase_34 AC 78 ms
55,920 KB
testcase_35 AC 79 ms
56,140 KB
testcase_36 AC 80 ms
58,188 KB
testcase_37 AC 42 ms
47,436 KB
testcase_38 AC 94 ms
48,176 KB
testcase_39 AC 368 ms
83,660 KB
testcase_40 AC 24 ms
37,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use max_flow::MaxFlow;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};

const M: usize = 500_001;

fn main() {
    input! {
        h: usize,
        w: usize,
        a: [[usize; w]; h],
    }
    let mut zh = vec![vec![]; M];
    let mut zw = vec![vec![]; M];
    let mut b = vec![vec![]; M];
    for i in 0..h {
        for j in 0..w {
            zh[a[i][j]].push(i);
            zw[a[i][j]].push(j);
            b[a[i][j]].push((i, j));
        }
    }
    for i in 0..M {
        zh[i].sort_unstable();
        zh[i].dedup();
        zw[i].sort_unstable();
        zw[i].dedup();
    }
    let mut res = 0;
    for x in 1..M {
        if zh[x].is_empty() {
            continue;
        }
        let mut g = MaxFlow::new(zh[x].len() + zw[x].len() + 2);
        let s = zh[x].len() + zw[x].len();
        let t = s + 1;
        for i in 0..zh[x].len() {
            g.add_edge(s, i, 1);
        }
        for i in 0..zw[x].len() {
            g.add_edge(i + zh[x].len(), t, 1);
        }
        for &(i, j) in &b[x] {
            let p = zh[x].binary_search(&i).unwrap();
            let q = zw[x].binary_search(&j).unwrap();
            g.add_edge(p, q + zh[x].len(), 1);
        }
        res += g.max_flow(s, t);
    }
    println!("{}", res);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `max-flow 0.1.0 (path+██████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::max_flow`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod max_flow {use std::collections::VecDeque;pub type FlowType=i64;const INF:FlowType=std::i64::MAX/2;pub struct MaxFlow{n:usize,edges:Vec<Edge_>,head:Vec<usize>,next:Vec<usize>,min_cost:Vec<i32>,iter:Vec<usize>,}#[derive(Debug,Clone,Copy)]pub struct Edge{pub from:usize,pub to:usize,pub cap:FlowType,pub flow:FlowType,}impl MaxFlow{pub fn new(n:usize)->Self{Self{n,edges:vec![],head:vec![!0;n],next:vec![],min_cost:vec![],iter:vec![],}}pub fn add_edge(&mut self,from:usize,to:usize,cap:FlowType)->usize{assert!(from!=to);assert!(from<self.n);assert!(to<self.n);assert!(cap>=0);let m=self.edges.len();self.next.push(self.head[from]);self.head[from]=m;self.next.push(self.head[to]);self.head[to]=m+1;self.edges.push(Edge_{to,cap});self.edges.push(Edge_{to:from,cap:0});m/2}pub fn max_flow(&mut self,s:usize,t:usize)->FlowType{assert!(s!=t);let max_cap=self.edges.iter().map(|e|e.cap).max().unwrap_or(0);if max_cap==0{return 0;}let mut flow=0;for i in(0..64-max_cap.leading_zeros()).rev(){let now=1<<i;while self.build_augment_path(s,t,now){self.iter=self.head.clone();flow+=self.find_augment_path(s,t,now,INF);}}flow}pub fn min_cut(&self,s:usize)->Vec<bool>{let mut vis=vec![false;self.n];let mut q=VecDeque::new();q.push_back(s);while let Some(v)=q.pop_front(){vis[v]=true;let mut e=self.head[v];while e!=!0{let Edge_{to,cap}=self.edges[e];if cap!=0&&!vis[to]{vis[to]=true;q.push_back(to);}e=self.next[e];}}vis}pub fn edges(&self)->Vec<Edge>{(0..self.edges.len()).step_by(2).map(|i|{let e=&self.edges[i];let f=&self.edges[i+1];Edge{from:f.to,to:e.to,cap:e.cap+f.cap,flow:f.cap,}}).collect()}fn build_augment_path(&mut self,s:usize,t:usize,base:FlowType)->bool{self.min_cost=vec![-1;self.n];let mut q=VecDeque::new();self.min_cost[s]=0;q.push_back(s);while q.len()>0&&self.min_cost[t]==-1{let v=q.pop_front().unwrap();let mut e=self.head[v];while e!=!0{let Edge_{to,cap}=self.edges[e];if cap>=base&&self.min_cost[to]==-1{self.min_cost[to]=self.min_cost[v]+1;q.push_back(to);}e=self.next[e];}}self.min_cost[t]!=-1}fn find_augment_path(&mut self,v:usize,t:usize,base:FlowType,flow:FlowType,)->FlowType{if v==t{return flow;}let mut sum=0;while self.iter[v]!=!0{let Edge_{to,cap}=self.edges[self.iter[v]];if cap>=base&&self.min_cost[v]<self.min_cost[to]{let d=self.find_augment_path(to,t,base,cap.min(flow-sum));if d>0{self.edges[self.iter[v]].cap-=d;self.edges[self.iter[v]^1].cap+=d;sum+=d;if flow-sum<base{break;}}}self.iter[v]=self.next[self.iter[v]];}sum}}struct Edge_{to:usize,cap:FlowType,}}
    }

    pub(crate) mod macros {
        pub mod max_flow {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod max_flow {}
    }
}
0