結果
| 問題 | No.2238 Rock and Hole |
| ユーザー |
 akakimidori
|
| 提出日時 | 2023-03-03 21:39:33 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 42 ms / 3,000 ms |
| コード長 | 8,455 bytes |
| コンパイル時間 | 13,377 ms |
| コンパイル使用メモリ | 387,944 KB |
| 実行使用メモリ | 14,848 KB |
| 最終ジャッジ日時 | 2024-09-17 22:33:31 |
| 合計ジャッジ時間 | 14,710 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 |
コンパイルメッセージ
warning: unused import: `std::io::Write` --> src/main.rs:8:5 | 8 | use std::io::Write; | ^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: type alias `Map` is never used --> src/main.rs:11:6 | 11 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:12:6 | 12 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:13:6 | 13 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
// 適当に辺張ってflowじゃダメなのか？// 向かい合うようなやつはバラせる// 巡回してるパターンは？// 四角形はバラせる// それ以外は？// とりあえず書いてみるかuse std::io::Write;use std::collections::*;type Map<K, V> = BTreeMap<K, V>;type Set<T> = BTreeSet<T>;type Deque<T> = VecDeque<T>;fn run() {input! {h: usize,w: usize,s: [bytes; h],}let mut g = maxflow::Graph::new(h * w + 2);let src = h * w;let dst = src + 1;for (i, s) in s.iter().enumerate() {for j in 0..w {if s[j] == b'h' {g.add_edge(i * w + j, dst, 1);for x in (0..j).rev().take_while(|x| s[*x] != b'h').filter(|&x| s[x] == b'r') {g.add_edge(i * w + x, i * w + j, 1);}for x in ((j + 1)..w).take_while(|x| s[*x] != b'h').filter(|&x| s[x] == b'r') {g.add_edge(i * w + x, i * w + j, 1);}} else if s[j] == b'r' {g.add_edge(src, i * w + j, 1);}}}for j in 0..w {for i in 0..h {if s[i][j] == b'h' {for x in (0..i).rev().take_while(|x| s[*x][j] != b'h').filter(|&x| s[x][j] == b'r') {g.add_edge(x * w + j, i * w + j, 1);}for x in ((i + 1)..h).take_while(|x| s[*x][j] != b'h').filter(|&x| s[x][j] == b'r') {g.add_edge(x * w + j, i * w + j, 1);}}}}let c = s.iter().flatten().filter(|c| **c == b'r').count() as i32;if g.flow(src, dst) == c {println!("Yes");} else {println!("No");}}fn main() {run();}// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------// ---------- begin max flow (Dinic) ----------mod maxflow {pub trait MaxFlowCapacity:Copy + Ord + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self>{fn zero() -> Self;fn inf() -> Self;}macro_rules! impl_primitive_integer_capacity {($x:ty, $y:expr) => {impl MaxFlowCapacity for $x {fn zero() -> Self {0}fn inf() -> Self {$y}}};}impl_primitive_integer_capacity!(u32, std::u32::MAX);impl_primitive_integer_capacity!(u64, std::u64::MAX);impl_primitive_integer_capacity!(i32, std::i32::MAX);impl_primitive_integer_capacity!(i64, std::i64::MAX);#[derive(Clone)]struct Edge<Cap> {to_: u32,inv_: u32,cap_: Cap,}impl<Cap> Edge<Cap> {fn new(to: usize, inv: usize, cap: Cap) -> Self {Edge {to_: to as u32,inv_: inv as u32,cap_: cap,}}fn to(&self) -> usize {self.to_ as usize}fn inv(&self) -> usize {self.inv_ as usize}}impl<Cap: MaxFlowCapacity> Edge<Cap> {fn add(&mut self, cap: Cap) {self.cap_ = self.cap_ + cap;}fn sub(&mut self, cap: Cap) {self.cap_ = self.cap_ - cap;}fn cap(&self) -> Cap {self.cap_}}pub struct Graph<Cap> {graph: Vec<Vec<Edge<Cap>>>,}#[allow(dead_code)]pub struct EdgeIndex {src: usize,dst: usize,x: usize,y: usize,}impl<Cap: MaxFlowCapacity> Graph<Cap> {pub fn new(size: usize) -> Self {Self {graph: vec![vec![]; size],}}pub fn add_edge(&mut self, src: usize, dst: usize, cap: Cap) -> EdgeIndex {assert!(src.max(dst) < self.graph.len());assert!(cap >= Cap::zero());assert!(src != dst);let x = self.graph[src].len();let y = self.graph[dst].len();self.graph[src].push(Edge::new(dst, y, cap));self.graph[dst].push(Edge::new(src, x, Cap::zero()));EdgeIndex { src, dst, x, y }}// src, dst, used, intial_capacity#[allow(dead_code)]pub fn get_edge(&self, e: &EdgeIndex) -> (usize, usize, Cap, Cap) {let max = self.graph[e.src][e.x].cap() + self.graph[e.dst][e.y].cap();let used = self.graph[e.dst][e.y].cap();(e.src, e.dst, used, max)}pub fn flow(&mut self, src: usize, dst: usize) -> Cap {let size = self.graph.len();assert!(src.max(dst) < size);assert!(src != dst);let mut queue = std::collections::VecDeque::new();let mut level = vec![0; size];let mut it = vec![0; size];let mut ans = Cap::zero();loop {(|| {level.clear();level.resize(size, 0);level[src] = 1;queue.clear();queue.push_back(src);while let Some(v) = queue.pop_front() {let d = level[v] + 1;for e in self.graph[v].iter() {let u = e.to();if e.cap() > Cap::zero() && level[u] == 0 {level[u] = d;if u == dst {return;}queue.push_back(u);}}}})();if level[dst] == 0 {break;}it.clear();it.resize(size, 0);loop {let f = self.dfs(dst, src, Cap::inf(), &mut it, &level);if f == Cap::zero() {break;}ans = ans + f;}}ans}fn dfs(&mut self, v: usize, src: usize, cap: Cap, it: &mut [usize], level: &[u32]) -> Cap {if v == src {return cap;}while let Some((u, inv)) = self.graph[v].get(it[v]).map(|p| (p.to(), p.inv())) {if level[u] + 1 == level[v] && self.graph[u][inv].cap() > Cap::zero() {let cap = cap.min(self.graph[u][inv].cap());let c = self.dfs(u, src, cap, it, level);if c > Cap::zero() {self.graph[v][it[v]].add(c);self.graph[u][inv].sub(c);return c;}}it[v] += 1;}Cap::zero()}}}// ---------- end max flow (Dinic) ----------