#1175102 (Rust) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: ngtkana
• 提出日時: 2026-08-06 03:11:44
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 121 ms / 2,000 ms
• コード長: 4,991 bytes
• コンパイル時間: 1,617 ms
• コンパイル使用メモリ: 203,580 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-06 03:11:51
• 合計ジャッジ時間: 5,093 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

use crate::max_flow::MaxFlow;
use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        d: u64,
        airplains: [(Usize1, Usize1, u64, u64, u64); m],
    }
    let mut counter = 0..;
    let nodes = vec_from_fn(2 * m, |_| counter.next().unwrap());
    let source = counter.next().unwrap();
    let sink = counter.next().unwrap();

    let mut events = vec![vec![]; n];
    let mut inst = MaxFlow::new();
    for (i, &(u, v, p, q, w)) in airplains.iter().enumerate() {
        events[u].push((2 * p + 1, nodes[2 * i]));
        events[v].push((2 * (q + d), nodes[2 * i + 1]));
        inst.add_edge(2 * i, 2 * i + 1, w);
    }
    for e in &mut events {
        e.sort_unstable();
        for ((_, x), (_, y)) in e.iter().copied().tuple_windows() {
            inst.add_edge(nodes[x], nodes[y], u64::MAX);
        }
    }
    if let Some(&(_, x)) = events[0].first() {
        inst.add_edge(source, x, u64::MAX);
    }
    if let Some(&(_, x)) = events[n - 1].last() {
        inst.add_edge(x, sink, u64::MAX);
    }
    let (flow, _cut) = inst.solve(counter.next().unwrap(), source, sink);

    println!("{flow}");
}

fn vec_from_fn<T>(len: usize, f: impl FnMut(usize) -> T) -> Vec<T> {
    (0..len).map(f).collect()
}

// max_flow {{{
// https://ngtkana.github.io/ac-adapter-rs/max_flow/index.html
#[allow(unused_imports)]
#[allow(dead_code)]
mod max_flow {
    use std::collections::{BinaryHeap, VecDeque};
    #[derive(Default, Debug)]
    pub struct MaxFlow {
        pub edges: Vec<Edge>,
    }
    impl MaxFlow {
        pub fn new() -> Self {
            Self::default()
        }
        pub fn add_edge(&mut self, src: usize, tar: usize, cap: u64) {
            self.edges.push(Edge {
                src,
                tar,
                cap,
                flow: 0,
            });
            self.edges.push(Edge {
                src: tar,
                tar: src,
                cap,
                flow: cap,
            });
        }
        pub fn original_edges(&self) -> Vec<Edge> {
            self.edges.iter().step_by(2).copied().collect()
        }
        pub fn solve(&mut self, n: usize, source: usize, sink: usize) -> (u64, Vec<bool>) {
            let Self { edges } = self;
            let mut g = vec![vec![]; n];
            for (i, &e) in edges.iter().enumerate() {
                g[e.src].push(i);
            }
            let mut excess = vec![0; n];
            for &i in &g[source] {
                let y = edges[i].tar;
                let f = edges[i].cap - edges[i].flow;
                if y == source || f == 0 {
                    continue;
                }
                excess[y] += f;
                edges[i].flow += f;
                edges[i ^ 1].flow -= f;
            }
            let mut height = vec![n + 1; n];
            let mut queue = VecDeque::new();
            height[source] = n;
            height[sink] = 0;
            queue.push_back(sink);
            while let Some(x) = queue.pop_front() {
                for &i in &g[x] {
                    let y = edges[i].tar;
                    if y != sink && height[y] == n + 1 && edges[i].flow != 0 {
                        height[y] = height[x] + 1;
                        queue.push_back(y);
                    }
                }
            }
            let mut heap = (0..n)
                .filter(|&x| x != source && x != sink && excess[x] != 0)
                .map(|x| (height[x], x))
                .collect::<BinaryHeap<_>>();
            'pop: while let Some((_, x)) = heap.pop() {
                for &i in &g[x] {
                    let y = edges[i].tar;
                    if edges[i].flow == edges[i].cap || height[x] <= height[y] {
                        continue;
                    }
                    let f = excess[x].min(edges[i].cap - edges[i].flow);
                    if excess[y] == 0 && y != source && y != sink {
                        heap.push((height[y], y));
                    }
                    edges[i].flow += f;
                    edges[i ^ 1].flow -= f;
                    excess[x] -= f;
                    excess[y] += f;
                    if excess[x] == 0 {
                        continue 'pop;
                    }
                }
                assert!(excess[x] > 0);
                height[x] = g[x]
                    .iter()
                    .filter(|&&i| edges[i].flow < edges[i].cap)
                    .map(|&i| height[edges[i].tar])
                    .min()
                    .unwrap()
                    + 1;
                heap.push((height[x], x));
            }
            let cut = height.iter().map(|&h| h >= n).collect();
            let flow = excess[sink];
            (flow, cut)
        }
    }
    #[derive(Debug, Default, Clone, Copy, PartialEq)]
    pub struct Edge {
        pub src: usize,
        pub tar: usize,
        pub cap: u64,
        pub flow: u64,
    }
}
// }}}