結果

問題 No.1479 Matrix Eraser
ユーザー 37kt
提出日時 2025-03-12 19:10:01
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 574 ms / 3,000 ms
コード長 12,295 bytes
コンパイル時間 14,732 ms
コンパイル使用メモリ 401,564 KB
実行使用メモリ 83,636 KB
最終ジャッジ日時 2025-03-12 19:10:28
合計ジャッジ時間 25,199 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// verification-helper: PROBLEM https://yukicoder.me/problems/no/1479
pub use __cargo_equip::prelude::*;
use max_flow::MaxFlow;
use proconio::{fastout, input};
const M: usize = 500_001;
#[fastout]
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();
        let ls = g.add_vertices(zh[x].len()).collect::<Vec<_>>();
        let rs = g.add_vertices(zw[x].len()).collect::<Vec<_>>();
        let src = g.add_vertex();
        let dst = g.add_vertex();
        for &v in &ls {
            g.add_edge(src, v, 1);
        }
        for &v in &rs {
            g.add_edge(v, dst, 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(ls[p], rs[q], 1);
        }
        res += g.max_flow(src, dst);
    }
    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`
///  - `numeric_traits 0.1.0 (path+██████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::__numeric_traits_0_1_0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod max_flow {use crate::__cargo_equip::preludes::max_flow::*;use std::iter::FusedIterator;use numeric_traits::{Inf,Integer};mod 
            internal{use crate::__cargo_equip::preludes::max_flow::*;#[derive(Clone,Copy)]pub(in crate::__cargo_equip::crates::max_flow)struct 
            Edge{pub(in crate::__cargo_equip::crates::max_flow)dst:usize,pub(in crate::__cargo_equip::crates::max_flow)cap:i64,}#[derive(Clone)]pub(in 
            crate::__cargo_equip::crates::max_flow)struct Queue{data:Vec<usize>,head:usize,tail:usize,}impl Queue{pub(in crate::__cargo_equip::crates
            ::max_flow)fn new()->Self{Self{data:vec![],head:0,tail:0,}}pub(in crate::__cargo_equip::crates::max_flow)fn set_capacity(&mut self,cap
            :usize){self.data.resize(cap,0);}pub(in crate::__cargo_equip::crates::max_flow)fn clear(&mut self){self.head=0;self.tail=0;}pub(in crate
            ::__cargo_equip::crates::max_flow)fn push(&mut self,v:usize){self.data[self.tail]=v;self.tail+=1;}pub(in crate::__cargo_equip::crates
            ::max_flow)fn pop(&mut self)->Option<usize>{(self.head!=self.tail).then(||{self.head+=1;self.data[self.head-1]})}}}#[derive(Clone)]pub 
            struct MaxFlow{edges:Vec<internal::Edge>,head:Vec<usize>,next:Vec<usize>,dist:Vec<i32>,iter:Vec<usize>,queue:internal::Queue,}#[derive
            (Debug,Clone,Copy)]pub struct Edge{pub src:usize,pub dst:usize,pub cap:i64,pub flow:i64,}impl MaxFlow{pub fn new()->Self{Self{edges:vec![]
            ,head:vec![],next:vec![],dist:vec![],iter:vec![],queue:internal::Queue::new(),}}pub fn count_vertices(&self)->usize{self.head.len()}pub fn 
            add_vertex(&mut self)->usize{self.head.push(!0);self.head.len()-1}pub fn add_vertices(&mut self,n:usize,)->impl Iterator<Item=usize
            >+DoubleEndedIterator+ExactSizeIterator+FusedIterator{self.head.resize(self.head.len()+n,!0);self.head.len()-n..self.head.len()}pub fn 
            add_edge(&mut self,src:usize,dst:usize,cap:i64)->usize{assert!(src!=dst);assert!(src<self.count_vertices());assert!(dst<self
            .count_vertices());assert!(cap>=0);let m=self.edges.len();self.next.push(self.head[src]);self.head[src]=m;self.next.push(self.head[dst]
            );self.head[dst]=m+1;self.edges.push(internal::Edge{dst,cap});self.edges.push(internal::Edge{dst:src,cap:0});m/2}pub fn edges(&self
            ,)->impl Iterator<Item=Edge>+DoubleEndedIterator+ExactSizeIterator+FusedIterator+'_{self.edges.windows(2).map(|e|Edge{src:e[1].dst,dst
            :e[0].dst,cap:e[0].cap+e[1].cap,flow:e[1].cap,})}pub fn max_flow(&mut self,src:usize,dst:usize)->i64{assert!(src!=dst);assert!(src<self
            .count_vertices());assert!(dst<self.count_vertices());let max_cap=self.edges.iter().map(|e|e.cap).max().unwrap_or(0);if max_cap==0{return 
            0;}self.iter.resize(self.count_vertices(),0);self.dist.resize(self.count_vertices(),0);let mut flow=0;for f in(0..=max_cap.floor_log2
            ()).map(|i|1<<i).rev(){while self.build_augmenting_path(src,dst,f){self.iter.copy_from_slice(&self.head);flow+=self.find_augmenting_path
            (src,dst,f,i64::inf());}}flow}pub fn min_cut(&mut self,src:usize)->Vec<bool>{let mut vis=vec![false;self.count_vertices()];self.queue
            .clear();self.queue.set_capacity(self.count_vertices());self.queue.push(src);while let Some(v)=self.queue.pop(){let mut ei=self.head[v]
            ;while ei!=!0{let e=self.edges[ei];if e.cap>0&&!vis[e.dst]{vis[e.dst]=true;self.queue.push(e.dst);}ei=self.next[ei];}}vis}fn 
            build_augmenting_path(&mut self,src:usize,dst:usize,base:i64)->bool{self.dist.fill(i32::inf());self.queue.clear();self.queue.set_capacity
            (self.count_vertices());self.dist[src]=0;self.queue.push(src);while let Some(v)=self.queue.pop(){let mut ei=self.head[v];while ei!=!0{let 
            e=self.edges[ei];if e.cap>=base&&self.dist[e.dst]==i32::inf(){self.dist[e.dst]=self.dist[v]+1;self.queue.push(e.dst);if e.dst==dst{return 
            true;}}ei=self.next[ei];}}false}fn find_augmenting_path(&mut self,v:usize,dst:usize,base:i64,flow:i64)->i64{if v==dst{return flow;}let mut 
            sum=0;while self.iter[v]!=!0{let e=self.edges[self.iter[v]];if e.cap>=base&&self.dist[v]<self.dist[e.dst]{let diff=self
            .find_augmenting_path(e.dst,dst,base,e.cap.min(flow-sum));if diff>0{self.edges[self.iter[v]].cap-=diff;self.edges[self.iter[v]^1].cap
            +=diff;sum+=diff;if flow-sum<base{break;}}}self.iter[v]=self.next[self.iter[v]];}sum}}}
        pub mod __numeric_traits_0_1_0 {pub mod inf{pub trait Inf:PartialOrd{fn inf()->Self;}pub trait NegInf:PartialOrd{fn neg_inf()->Self
            ;}macro_rules!impl_inf{($($t:ty,$inf:expr,)*)=>{$(impl Inf for$t{fn inf()->Self{$inf}})*}}macro_rules!impl_neg_inf{($($t:ty,$neg_inf:expr
            ,)*)=>{$(impl NegInf for$t{fn neg_inf()->Self{$neg_inf}})*}}impl_inf!{i32,1_001_000_000,u32,1_001_000_000,f32,1e10,i64
            ,4_004_000_000_000_000_000,isize,4_004_000_000_000_000_000,u64,4_004_000_000_000_000_000,usize,4_004_000_000_000_000_000,f64,1e20,i128
            ,8_008_000_000_000_000_000_000_000_000_000_000_000,u128,8_008_000_000_000_000_000_000_000_000_000_000_000,}impl_neg_inf!{i32
            ,-1_001_000_000,u32,0,f32,-1e10,i64,-4_004_000_000_000_000_000,isize,-4_004_000_000_000_000_000,u64,0,usize,0,f64,-1e20,i128
            ,-8_008_000_000_000_000_000_000_000_000_000_000_000,u128,0,}}pub use inf::*;pub mod zero_one{use std::ops::{Add,Mul};pub trait Zero:Sized
            +Add<Output=Self>{fn zero()->Self;}pub trait One:Sized+Mul<Output=Self>{fn one()->Self;}macro_rules!impl_zero_one{($($t:ty),*)=>{$(impl 
            Zero for$t{fn zero()->Self{0 as$t}}impl One for$t{fn one()->Self{1 as$t}})*}}impl_zero_one!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128
            ,isize,f32,f64);}pub use zero_one::*;pub mod cast{pub trait Cast<T>{fn cast(self)->T;}macro_rules!impl_cast_2{($t1:ty,$($t2:ty),*)=>{$
            (impl Cast<$t2>for$t1{fn cast(self)->$t2{self as$t2}})*}}macro_rules!impl_cast_1{($($t:ty),*)=>{$(impl_cast_2!{$t,u8,u16,u32,u64,u128,i8
            ,i16,i32,i64,i128,usize,isize,f32,f64})*}}impl_cast_1!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64}}pub use cast::*;pub 
            mod numeric{use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};use crate::__cargo_equip::crates
            ::__numeric_traits_0_1_0::zero_one;pub trait Numeric:Sized+Clone+Copy+std::fmt::Debug+std::fmt::Display+PartialEq+Add<Output=Self
            >+AddAssign+Sub<Output=Self>+SubAssign+Mul<Output=Self>+MulAssign+Div<Output=Self>+DivAssign+zero_one::Zero+zero_one
            ::One{}macro_rules!impl_numeric{($($t:ty),*)=>{$(impl Numeric for$t{})*};}impl_numeric!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize
            ,isize,f32,f64}}pub use numeric::*;pub mod integer{use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Rem,RemAssign
            ,Shl,ShlAssign,Shr,ShrAssign,};use crate::__cargo_equip::crates::__numeric_traits_0_1_0::Numeric;pub trait Integer:Numeric+Eq+Ord+std
            ::hash::Hash+Rem<Output=Self>+RemAssign+BitXor<Output=Self>+BitXorAssign+BitAnd<Output=Self>+BitAndAssign+BitOr<Output=Self>+BitOrAssign
            +Shl<usize,Output=Self>+ShlAssign<usize>+Shr<usize,Output=Self>+ShrAssign<usize>{fn popcount(self)->usize;fn msb_index(self)->usize;fn 
            lsb_index(self)->usize;fn msb(self)->Self;fn lsb(self)->Self;fn ceil_pow2(self)->Self;fn floor_pow2(self)->Self;fn ceil_log2(self)->usize
            ;fn floor_log2(self)->usize;fn checked_msb_index(self)->Option<usize>;fn checked_lsb_index(self)->Option<usize>;fn checked_ceil_pow2(self
            )->Option<Self>;fn checked_floor_pow2(self)->Option<Self>;fn checked_ceil_log2(self)->Option<usize>;fn checked_floor_log2(self)->Option
            <usize>;fn floor_div(self,other:Self)->Self;fn ceil_div(self,other:Self)->Self;fn gcd(self,other:Self)->Self;fn lcm(self,other:Self)->Self
            ;}macro_rules!impl_integer{($($t:ty),*)=>{$(impl Integer for$t{fn popcount(self)->usize{self.count_ones()as usize}fn msb_index(self
            )->usize{(<$t>::BITS-1-self.leading_zeros())as usize}fn lsb_index(self)->usize{self.trailing_zeros()as usize}fn msb(self)->Self{if self
            ==0{0}else{1<<self.msb_index()}}fn lsb(self)->Self{self&self.wrapping_neg()}fn ceil_pow2(self)->Self{1<<self.ceil_log2()}fn floor_pow2
            (self)->Self{assert!(self>0);self.msb()}fn ceil_log2(self)->usize{assert!(self>0);(<$t>::BITS-(self-1).leading_zeros())as usize}fn 
            floor_log2(self)->usize{assert!(self>0);self.msb_index()}fn checked_msb_index(self)->Option<usize>{if self==0{None}else{Some(self
            .msb_index())}}fn checked_lsb_index(self)->Option<usize>{if self==0{None}else{Some(self.lsb_index())}}fn checked_ceil_pow2(self)->Option
            <Self>{if self<=0{None}else{Some(self.ceil_pow2())}}fn checked_floor_pow2(self)->Option<Self>{if self<=0{None}else{Some(self.floor_pow2
            ())}}fn checked_ceil_log2(self)->Option<usize>{if self<=0{None}else{Some(self.ceil_log2())}}fn checked_floor_log2(self)->Option<usize>{if 
            self<=0{None}else{Some(self.floor_log2())}}#[allow(unused_comparisons)]fn floor_div(self,other:Self)->Self{self/other-if self^other
            <0&&self%other!=0{1}else{0}}#[allow(unused_comparisons)]fn ceil_div(self,other:Self)->Self{self/other+if self^other>=0&&self%other!
            =0{1}else{0}}#[allow(unused_comparisons)]fn gcd(self,other:Self)->Self{let mut x=if self<0{0-self}else{self};let mut y=if other<0{0
            -other}else{other};if x==0||y==0{return x|y;}let n=x.trailing_zeros();let m=y.trailing_zeros();x>>=n;y>>=m;while x!=y{if x>y{x-=y;x>>=x
            .trailing_zeros();}else{y-=x;y>>=y.trailing_zeros();}}x<<n.min(m)}fn lcm(self,other:Self)->Self{self/self.gcd(other)*other}})*}
            ;}impl_integer!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize}}pub use integer::*;pub mod signed{use std::ops::Neg;pub trait Signed
            :Sized+Neg<Output=Self>{fn signum(self)->Self;}macro_rules!impl_signed_integer{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self
            )->Self{match self{n if n>0=>1,0=>0,_=>-1,}}})*};}macro_rules!impl_signed_float{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self
            )->Self{if self.is_nan(){self}else if self==0.0{0.0}else if self>0.0{1.0}else{-1.0}}})*};}impl_signed_integer!{i8,i16,i32,i64,i128
            ,isize}impl_signed_float!{f32,f64}}pub use signed::*;pub trait Recip{fn recip(self)->Self;}impl Recip for f32{fn recip(self)->Self{self
            .recip()}}impl Recip for f64{fn recip(self)->Self{self.recip()}}}
    }
    pub(crate) mod macros {
        pub mod max_flow {}
        pub mod __numeric_traits_0_1_0 {}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
    mod preludes {
        pub mod max_flow {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__numeric_traits_0_1_0 as numeric_traits;}
        pub mod __numeric_traits_0_1_0 {}
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0