結果

問題 No.1479 Matrix Eraser
ユーザー 37kt
提出日時 2025-03-12 19:08:37
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 12,329 bytes
コンパイル時間 15,194 ms
コンパイル使用メモリ 392,568 KB
実行使用メモリ 55,484 KB
最終ジャッジ日時 2025-03-12 19:09:04
合計ジャッジ時間 24,751 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

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{eprintln!("{} {} {}",src,dst,cap);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 {}
    }
}
0