結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー | akakimidori |
提出日時 | 2021-01-15 22:49:00 |
言語 | Rust (1.77.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,855 bytes |
コンパイル時間 | 14,635 ms |
コンパイル使用メモリ | 376,892 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-05-05 00:49:52 |
合計ジャッジ時間 | 21,043 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
10,752 KB |
testcase_01 | AC | 0 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 14 ms
5,376 KB |
testcase_07 | TLE | - |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
ソースコード
// 最短路反復法 // src -> dst へflowだけ流せた時コストを返す // 負閉路はないと仮定 const INF: i64 = 1_000_000_000_000_000i64 + 1; struct Graph { size: usize, edge: Vec<(usize, usize, i64, i64)>, } impl Graph { fn new(size: usize) -> Self { Graph { size: size, edge: vec![], } } fn add_edge(&mut self, src: usize, dst: usize, capa: i64, cost: i64) { assert!(src < self.size && dst < self.size && src != dst); self.edge.push((src, dst, capa, cost)); } fn flow(&self, src: usize, dst: usize, flow: i64) -> Result<i64, (i64, i64)> { if src == dst { return Ok(0); } let size = self.size; let edge = &self.edge; let mut deg = vec![0; size]; for &(a, b, _, _) in edge.iter() { deg[a] += 1; deg[b] += 1; } let mut graph: Vec<_> = deg.into_iter().map(|d| Vec::with_capacity(d)).collect(); for &(a, b, capa, cost) in edge.iter() { let x = graph[a].len(); let y = graph[b].len(); graph[a].push((b, capa, cost, y)); graph[b].push((a, 0, -cost, x)); } let mut ans = 0; let mut rem = flow; let mut dp = Vec::with_capacity(size); let mut pot = vec![0; size]; let mut h = std::collections::BinaryHeap::new(); while rem > 0 { dp.clear(); dp.resize(size, (INF, src, 0));// コスト、親、親からの番号 dp[src] = (0, src, 0); h.push((0, src)); while let Some((d, v)) = h.pop() { let d = -d; if d > dp[v].0 { continue; } for (i, &(u, capa, cost, _)) in graph[v].iter().enumerate() { if capa == 0 { continue; } let c = d + cost - pot[u] + pot[v]; if c < dp[u].0 { dp[u] = (c, v, i); h.push((-c, u)); } } } if dp[dst].0 == INF { return Err((flow - rem, ans)); } for i in 0..size { pot[i] -= dp[dst].0 - dp[i].0; } let mut sub = rem; let mut pos = dst; while pos != src { let (_, parent, k) = dp[pos]; sub = sub.min(graph[parent][k].1); pos = parent; } let mut pos = dst; while pos != src { let (_, parent, k) = dp[pos]; let inv = graph[parent][k].3; graph[parent][k].1 -= sub; graph[pos][inv].1 += sub; pos = parent; } rem -= sub; ans += -pot[src] * sub; } Ok(ans) } } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 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_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_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 ---------- fn run() { input! { n: usize, m: i64, p: [(i64, i64, i64); n], } let mut b = p.iter().map(|p| p.1).collect::<Vec<_>>(); b.sort(); let mut p = p.iter().enumerate().map(|(k, p)| (p.0.min(p.2), p.0.max(p.2), k)).collect::<Vec<_>>(); let mut g = Graph::new(4 * n + 2); let src = 4 * n; let dst = src + 1; let geta = 1_000_000_000; for i in 0..n { g.add_edge(src, i, 1, 0); } p.sort_by_key(|p| p.1); for i in 1..n { g.add_edge(n + p[i].2, n + p[i - 1].2, 3000, 0); } let mut x = n; for &(_a, c, k) in p.iter().rev() { g.add_edge(n + k, 2 * n + k, 1, 0); while x > 0 && b[x - 1] > c { x -= 1; g.add_edge(x, n + k, 1, geta - b[x]); } } p.sort_by_key(|p| p.0); for i in 0..(n - 1) { g.add_edge(3 * n + p[i].2, 3 * n + p[i + 1].2, 3000, 0); } let mut x = 0; for &(a, c, k) in p.iter() { g.add_edge(3 * n + k, 2 * n + k, 1, geta - c); while x < n && b[x] < a { g.add_edge(x, 3 * n + k, 1, 0); x += 1; } } for i in 0..n { g.add_edge(2 * n + i, dst, 1, 0); } if let Ok(ans) = g.flow(src, dst, n as i64) { println!("YES"); if n as i64 * geta - ans >= m { println!("KADOMATSU!"); } else { println!("NO"); } } else { println!("NO"); } } fn main() { run(); }