結果

問題 No.1479 Matrix Eraser
ユーザー 37kt
提出日時 2025-03-18 10:58:43
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 519 ms / 3,000 ms
コード長 12,894 bytes
コンパイル時間 14,032 ms
コンパイル使用メモリ 402,040 KB
実行使用メモリ 83,688 KB
最終ジャッジ日時 2025-03-18 10:59:41
合計ジャッジ時間 25,028 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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());
        let rs = g.add_vertices(zw[x].len());
        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, None);
    }
    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::Integer;mod graph{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,pub(in crate::__cargo_equip::crates
            ::max_flow)rev:usize,}}mod queue{use crate::__cargo_equip::preludes::max_flow::*;#[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<Vec<graph::Edge>>,pos:Vec<(usize,usize)>,iter:Vec<usize>,dist:Vec<u64>,queue:queue::Queue,zero:u64,src:Option<usize>,}#[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![],pos
            :vec![],iter:vec![],dist:vec![],queue:queue::Queue::new(),zero:1<<60,src:None,}}pub fn num_vertices(&self)->usize{self.edges.len()}pub fn 
            num_edges(&self)->usize{self.pos.len()}pub fn add_vertex(&mut self)->usize{self.src=None;let v=self.edges.len();self.edges.push(vec![]
            );self.iter.push(0);self.dist.push(self.zero);v}pub fn add_vertices(&mut self,n:usize)->Vec<usize>{self.src=None;let v=self.edges.len
            ();self.edges.resize(v+n,vec![]);self.iter.resize(v+n,0);self.dist.resize(v+n,self.zero);(v..v+n).collect()}pub fn add_edge(&mut self,src
            :usize,dst:usize,cap:i64)->usize{assert!(src<self.num_vertices());assert!(dst<self.num_vertices());assert!(cap>=0);self.src=None;let e
            =self.pos.len();let i=self.edges[src].len();let j=self.edges[dst].len()+if src==dst{1}else{0};self.edges[src].push(graph::Edge{dst,cap,rev
            :j});self.edges[dst].push(graph::Edge{dst:src,cap:0,rev:i,});self.pos.push((src,i));e}pub fn edge(&self,e:usize)->Edge{let(src,i)=self
            .pos[e];let e1=self.edges[src][i];let e2=self.edges[e1.dst][e1.rev];Edge{src,dst:e1.dst,cap:e1.cap+e2.cap,flow:e2.cap,}}pub fn edges(&self
            ,)->impl Iterator<Item=Edge>+DoubleEndedIterator+ExactSizeIterator+FusedIterator+'_{(0..self.num_edges()).map(|e|self.edge(e))}pub fn 
            max_flow(&mut self,src:usize,dst:usize,limit:Option<i64>)->i64{assert!(src!=dst);assert!(src<self.num_vertices());assert!(dst<self
            .num_vertices());self.src=Some(src);let limit=limit.unwrap_or(i64::MAX);let max_cap=self.edges.iter().flatten().map(|e|e.cap).max
            ().unwrap_or(0);if max_cap==0{return 0;}let mut flow=0;for f in(0..=limit.min(max_cap).floor_log2()).map(|i|1<<i).rev(){while flow<=limit
            -f&&self.build_augmenting_path(src,dst,f){self.iter.fill(0);flow+=self.find_augmenting_path(src,dst,f,limit-flow);}}flow}pub fn min_cut
            (&mut self)->Vec<usize>{let src=self.src.expect("max_flow is not called");let mut res=vec![1;self.num_vertices()];self.queue.clear();self
            .queue.set_capacity(self.num_vertices());res[src]=0;self.queue.push(src);while let Some(v)=self.queue.pop(){for e in&self.edges[v]{if e
            .cap>0&&res[e.dst]==1{res[e.dst]=0;self.queue.push(e.dst);}}}res}fn build_augmenting_path(&mut self,src:usize,dst:usize,base:i64
            )->bool{self.zero-=1<<30;self.queue.clear();self.queue.set_capacity(self.num_vertices());self.dist[src]=self.zero;self.queue.push(src
            );while let Some(v)=self.queue.pop(){for e in&self.edges[v]{if e.cap>=base&&self.dist[e.dst]>self.dist[v]+1{self.dist[e.dst]=self.dist[v]
            +1;self.queue.push(e.dst);if e.dst==dst{return true;}}}}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]<self.edges[v].len(){let e=self.edges[v][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[v][self.iter[v]].cap
            -=diff;self.edges[e.dst][e.rev].cap+=diff;sum+=diff;if flow-sum<base{break;}}}self.iter[v]+=1;}sum}}#[test]fn test(){let mut flow=MaxFlow
            ::new();let src=flow.add_vertex();let dst=flow.add_vertex();flow.add_edge(src,dst,i64::MAX);flow.add_edge(src,dst,i64::MAX);let f=flow
            .max_flow(src,dst,None);assert_eq!(f,i64::MAX);let f=flow.max_flow(src,dst,None);assert_eq!(f,i64::MAX);let f=flow.max_flow(src,dst,Some(1
            <<20));assert_eq!(f,0);}}
        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