結果
| 問題 |
No.1479 Matrix Eraser
|
| コンテスト | |
| ユーザー |
 fukafukatani
|
| 提出日時 | 2021-04-17 10:51:57 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 284 ms / 3,000 ms |
| コード長 | 18,731 bytes |
| コンパイル時間 | 13,215 ms |
| コンパイル使用メモリ | 399,264 KB |
| 実行使用メモリ | 45,212 KB |
| 最終ジャッジ日時 | 2024-07-03 17:32:27 |
| 合計ジャッジ時間 | 19,613 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 39 |
ソースコード
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;
use std::ops::Bound::*;
#[allow(unused_macros)]
macro_rules! debug {
($($e:expr),*) => {
#[cfg(debug_assertions)]
$({
let (e, mut err) = (stringify!($e), std::io::stderr());
writeln!(err, "{} = {:?}", e, $e).unwrap()
})*
};
}
fn main() {
let v = read_vec::<usize>();
let (h, w) = (v[0], v[1]);
let mut poses = HashMap::new();
for y in 0..h {
let row = read_vec::<i64>();
for x in 0..w {
if row[x] == 0 {
continue;
}
poses.entry(row[x]).or_insert(vec![]).push((x, y));
}
}
let mut ans = 0;
for ref v in poses.values() {
let mut used_x = vec![];
let mut used_y = vec![];
for &(x, y) in *v {
used_x.push(x);
used_y.push(y);
}
used_x.sort();
used_x.dedup();
let mut x_comp = HashMap::new();
for i in 0..used_x.len() {
x_comp.insert(used_x[i], i);
}
let mut y_comp = HashMap::new();
used_y.sort();
used_y.dedup();
for i in 0..used_y.len() {
y_comp.insert(used_y[i], i);
}
let h = y_comp.len();
let w = x_comp.len();
let s = h + w;
let t = h + w + 1;
let mut flow = MfGraph::new(h + w + 2);
for y in 0..h {
flow.add_edge(s, y, 1);
}
for x in 0..w {
flow.add_edge(h + x, t, 1);
}
for &(x, y) in *v {
flow.add_edge(y_comp[&y], h + x_comp[&x], 1);
}
let m = flow.flow(s, t);
// debug!(m, v);
ans += m;
}
println!("{}", ans);
}
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
//https://github.com/rust-lang-ja/ac-library-rs
pub mod internal_queue {
#![allow(dead_code)]
#[derive(Default)]
pub(crate) struct SimpleQueue<T> {
payload: Vec<T>,
pos: usize,
}
impl<T> SimpleQueue<T> {
pub(crate) fn reserve(&mut self, n: usize) {
if n > self.payload.len() {
self.payload.reserve(n - self.payload.len());
}
}
pub(crate) fn size(&self) -> usize {
self.payload.len() - self.pos
}
pub(crate) fn empty(&self) -> bool {
self.pos == self.payload.len()
}
pub(crate) fn push(&mut self, t: T) {
self.payload.push(t);
}
// Do we need mutable version?
pub(crate) fn front(&self) -> Option<&T> {
if self.pos < self.payload.len() {
Some(&self.payload[self.pos])
} else {
None
}
}
pub(crate) fn clear(&mut self) {
self.payload.clear();
self.pos = 0;
}
pub(crate) fn pop(&mut self) -> Option<&T> {
if self.pos < self.payload.len() {
self.pos += 1;
Some(&self.payload[self.pos - 1])
} else {
None
}
}
}
#[cfg(test)]
mod test {
use crate::internal_queue::SimpleQueue;
#[allow(clippy::cognitive_complexity)]
#[test]
fn test_simple_queue() {
let mut queue = SimpleQueue::default();
assert_eq!(queue.size(), 0);
assert!(queue.empty());
assert!(queue.front().is_none());
assert!(queue.pop().is_none());
queue.push(123);
assert_eq!(queue.size(), 1);
assert!(!queue.empty());
assert_eq!(queue.front(), Some(&123));
queue.push(456);
assert_eq!(queue.size(), 2);
assert!(!queue.empty());
assert_eq!(queue.front(), Some(&123));
assert_eq!(queue.pop(), Some(&123));
assert_eq!(queue.size(), 1);
assert!(!queue.empty());
assert_eq!(queue.front(), Some(&456));
queue.push(789);
queue.push(789);
queue.push(456);
queue.push(456);
assert_eq!(queue.size(), 5);
assert!(!queue.empty());
assert_eq!(queue.front(), Some(&456));
assert_eq!(queue.pop(), Some(&456));
assert_eq!(queue.size(), 4);
assert!(!queue.empty());
assert_eq!(queue.front(), Some(&789));
queue.clear();
assert_eq!(queue.size(), 0);
assert!(queue.empty());
assert!(queue.front().is_none());
assert!(queue.pop().is_none());
}
}
}
pub mod internal_type_traits {
use std::{
fmt,
iter::{Product, Sum},
ops::{
Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
SubAssign,
},
};
// Skipped:
//
// - `is_signed_int_t<T>` (probably won't be used directly in `modint.rs`)
// - `is_unsigned_int_t<T>` (probably won't be used directly in `modint.rs`)
// - `to_unsigned_t<T>` (not used in `fenwicktree.rs`)
/// Corresponds to `std::is_integral` in C++.
// We will remove unnecessary bounds later.
//
// Maybe we should rename this to `PrimitiveInteger` or something, as it probably won't be used in the
// same way as the original ACL.
pub trait Integral:
'static
+ Send
+ Sync
+ Copy
+ Ord
+ Not<Output = Self>
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ Rem<Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ RemAssign
+ Sum
+ Product
+ BitOr<Output = Self>
+ BitAnd<Output = Self>
+ BitXor<Output = Self>
+ BitOrAssign
+ BitAndAssign
+ BitXorAssign
+ Shl<Output = Self>
+ Shr<Output = Self>
+ ShlAssign
+ ShrAssign
+ fmt::Display
+ fmt::Debug
+ fmt::Binary
+ fmt::Octal
+ Zero
+ One
+ BoundedBelow
+ BoundedAbove
{
}
/// Class that has additive identity element
pub trait Zero {
/// The additive identity element
fn zero() -> Self;
}
/// Class that has multiplicative identity element
pub trait One {
/// The multiplicative identity element
fn one() -> Self;
}
pub trait BoundedBelow {
fn min_value() -> Self;
}
pub trait BoundedAbove {
fn max_value() -> Self;
}
macro_rules! impl_integral {
($($ty:ty),*) => {
$(
impl Zero for $ty {
#[inline]
fn zero() -> Self {
0
}
}
impl One for $ty {
#[inline]
fn one() -> Self {
1
}
}
impl BoundedBelow for $ty {
#[inline]
fn min_value() -> Self {
Self::min_value()
}
}
impl BoundedAbove for $ty {
#[inline]
fn max_value() -> Self {
Self::max_value()
}
}
impl Integral for $ty {}
)*
};
}
impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
}
pub mod maxflow {
#![allow(dead_code)]
use crate::internal_queue::SimpleQueue;
use crate::internal_type_traits::Integral;
use std::cmp::min;
use std::iter;
impl<Cap> MfGraph<Cap>
where
Cap: Integral,
{
pub fn new(n: usize) -> MfGraph<Cap> {
MfGraph {
_n: n,
pos: Vec::new(),
g: iter::repeat_with(Vec::new).take(n).collect(),
}
}
pub fn add_edge(&mut self, from: usize, to: usize, cap: Cap) -> usize {
assert!(from < self._n);
assert!(to < self._n);
assert!(Cap::zero() <= cap);
let m = self.pos.len();
self.pos.push((from, self.g[from].len()));
let rev = self.g[to].len() + if from == to { 1 } else { 0 };
self.g[from].push(_Edge { to, rev, cap });
let rev = self.g[from].len() - 1;
self.g[to].push(_Edge {
to: from,
rev,
cap: Cap::zero(),
});
m
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct Edge<Cap: Integral> {
pub from: usize,
pub to: usize,
pub cap: Cap,
pub flow: Cap,
}
impl<Cap> MfGraph<Cap>
where
Cap: Integral,
{
pub fn get_edge(&self, i: usize) -> Edge<Cap> {
let m = self.pos.len();
assert!(i < m);
let _e = &self.g[self.pos[i].0][self.pos[i].1];
let _re = &self.g[_e.to][_e.rev];
Edge {
from: self.pos[i].0,
to: _e.to,
cap: _e.cap + _re.cap,
flow: _re.cap,
}
}
pub fn edges(&self) -> Vec<Edge<Cap>> {
let m = self.pos.len();
(0..m).map(|i| self.get_edge(i)).collect()
}
pub fn change_edge(&mut self, i: usize, new_cap: Cap, new_flow: Cap) {
let m = self.pos.len();
assert!(i < m);
assert!(Cap::zero() <= new_flow && new_flow <= new_cap);
let (to, rev) = {
let _e = &mut self.g[self.pos[i].0][self.pos[i].1];
_e.cap = new_cap - new_flow;
(_e.to, _e.rev)
};
let _re = &mut self.g[to][rev];
_re.cap = new_flow;
}
/// `s != t` must hold, otherwise it panics.
pub fn flow(&mut self, s: usize, t: usize) -> Cap {
self.flow_with_capacity(s, t, Cap::max_value())
}
/// # Parameters
/// * `s != t` must hold, otherwise it panics.
/// * `flow_limit >= 0`
pub fn flow_with_capacity(&mut self, s: usize, t: usize, flow_limit: Cap) -> Cap {
let n_ = self._n;
assert!(s < n_);
assert!(t < n_);
// By the definition of max flow in appendix.html, this function should return 0
// when the same vertices are provided. On the other hand, it is reasonable to
// return infinity-like value too, which is what the original implementation
// (and this implementation without the following assertion) does.
// Since either return value is confusing, we'd rather deny the parameters
// of the two same vertices.
// For more details, see https://github.com/rust-lang-ja/ac-library-rs/pull/24#discussion_r485343451
// and https://github.com/atcoder/ac-library/issues/5 .
assert_ne!(s, t);
// Additional constraint
assert!(Cap::zero() <= flow_limit);
let mut calc = FlowCalculator {
graph: self,
s,
t,
flow_limit,
level: vec![0; n_],
iter: vec![0; n_],
que: SimpleQueue::default(),
};
let mut flow = Cap::zero();
while flow < flow_limit {
calc.bfs();
if calc.level[t] == -1 {
break;
}
calc.iter.iter_mut().for_each(|e| *e = 0);
while flow < flow_limit {
let f = calc.dfs(t, flow_limit - flow);
if f == Cap::zero() {
break;
}
flow += f;
}
}
flow
}
pub fn min_cut(&self, s: usize) -> Vec<bool> {
let mut visited = vec![false; self._n];
let mut que = SimpleQueue::default();
que.push(s);
while !que.empty() {
let &p = que.front().unwrap();
que.pop();
visited[p] = true;
for e in &self.g[p] {
if e.cap != Cap::zero() && !visited[e.to] {
visited[e.to] = true;
que.push(e.to);
}
}
}
visited
}
}
struct FlowCalculator<'a, Cap> {
graph: &'a mut MfGraph<Cap>,
s: usize,
t: usize,
flow_limit: Cap,
level: Vec<i32>,
iter: Vec<usize>,
que: SimpleQueue<usize>,
}
impl<Cap> FlowCalculator<'_, Cap>
where
Cap: Integral,
{
fn bfs(&mut self) {
self.level.iter_mut().for_each(|e| *e = -1);
self.level[self.s] = 0;
self.que.clear();
self.que.push(self.s);
while !self.que.empty() {
let v = *self.que.front().unwrap();
self.que.pop();
for e in &self.graph.g[v] {
if e.cap == Cap::zero() || self.level[e.to] >= 0 {
continue;
}
self.level[e.to] = self.level[v] + 1;
if e.to == self.t {
return;
}
self.que.push(e.to);
}
}
}
fn dfs(&mut self, v: usize, up: Cap) -> Cap {
if v == self.s {
return up;
}
let mut res = Cap::zero();
let level_v = self.level[v];
for i in self.iter[v]..self.graph.g[v].len() {
self.iter[v] = i;
let &_Edge {
to: e_to,
rev: e_rev,
..
} = &self.graph.g[v][i];
if level_v <= self.level[e_to] || self.graph.g[e_to][e_rev].cap == Cap::zero() {
continue;
}
let d = self.dfs(e_to, min(up - res, self.graph.g[e_to][e_rev].cap));
if d <= Cap::zero() {
continue;
}
self.graph.g[v][i].cap += d;
self.graph.g[e_to][e_rev].cap -= d;
res += d;
if res == up {
break;
}
}
self.iter[v] = self.graph.g[v].len();
res
}
}
#[derive(Default)]
pub struct MfGraph<Cap> {
_n: usize,
pos: Vec<(usize, usize)>,
g: Vec<Vec<_Edge<Cap>>>,
}
struct _Edge<Cap> {
to: usize,
rev: usize,
cap: Cap,
}
#[cfg(test)]
mod test {
use crate::{Edge, MfGraph};
#[test]
fn test_max_flow_wikipedia() {
// From https://commons.wikimedia.org/wiki/File:Min_cut.png
// Under CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0/deed.en
let mut graph = MfGraph::new(6);
assert_eq!(graph.add_edge(0, 1, 3), 0);
assert_eq!(graph.add_edge(0, 2, 3), 1);
assert_eq!(graph.add_edge(1, 2, 2), 2);
assert_eq!(graph.add_edge(1, 3, 3), 3);
assert_eq!(graph.add_edge(2, 4, 2), 4);
assert_eq!(graph.add_edge(3, 4, 4), 5);
assert_eq!(graph.add_edge(3, 5, 2), 6);
assert_eq!(graph.add_edge(4, 5, 3), 7);
assert_eq!(graph.flow(0, 5), 5);
let edges = graph.edges();
{
#[rustfmt::skip]
assert_eq!(
edges,
vec![
Edge { from: 0, to: 1, cap: 3, flow: 3 },
Edge { from: 0, to: 2, cap: 3, flow: 2 },
Edge { from: 1, to: 2, cap: 2, flow: 0 },
Edge { from: 1, to: 3, cap: 3, flow: 3 },
Edge { from: 2, to: 4, cap: 2, flow: 2 },
Edge { from: 3, to: 4, cap: 4, flow: 1 },
Edge { from: 3, to: 5, cap: 2, flow: 2 },
Edge { from: 4, to: 5, cap: 3, flow: 3 },
]
);
}
assert_eq!(
graph.min_cut(0),
vec![true, false, true, false, false, false]
);
}
#[test]
fn test_max_flow_wikipedia_multiple_edges() {
// From https://commons.wikimedia.org/wiki/File:Min_cut.png
// Under CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0/deed.en
let mut graph = MfGraph::new(6);
for &(u, v, c) in &[
(0, 1, 3),
(0, 2, 3),
(1, 2, 2),
(1, 3, 3),
(2, 4, 2),
(3, 4, 4),
(3, 5, 2),
(4, 5, 3),
] {
for _ in 0..c {
graph.add_edge(u, v, 1);
}
}
assert_eq!(graph.flow(0, 5), 5);
assert_eq!(
graph.min_cut(0),
vec![true, false, true, false, false, false]
);
}
#[test]
#[allow(clippy::many_single_char_names)]
fn test_max_flow_misawa() {
// Originally by @MiSawa
// From https://gist.github.com/MiSawa/47b1d99c372daffb6891662db1a2b686
let n = 100;
let mut graph = MfGraph::new((n + 1) * 2 + 5);
let (s, a, b, c, t) = (0, 1, 2, 3, 4);
graph.add_edge(s, a, 1);
graph.add_edge(s, b, 2);
graph.add_edge(b, a, 2);
graph.add_edge(c, t, 2);
for i in 0..n {
let i = 2 * i + 5;
for j in 0..2 {
for k in 2..4 {
graph.add_edge(i + j, i + k, 3);
}
}
}
for j in 0..2 {
graph.add_edge(a, 5 + j, 3);
graph.add_edge(2 * n + 5 + j, c, 3);
}
assert_eq!(graph.flow(s, t), 2);
}
}
}
use maxflow::*;