#1175503 (Rust) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: ngtkana
• 提出日時: 2026-08-06 18:48:02
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 28 ms / 2,000 ms
• コード長: 3,385 bytes
• コンパイル時間: 12,055 ms
• コンパイル使用メモリ: 199,572 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-06 18:48:17
• 合計ジャッジ時間: 10,315 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

use itertools::Itertools;
use proconio::{input, marker::Usize1};
use std::collections::VecDeque;

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 {
        g: vec![vec![]; counter.start],
    };
    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 = inst.solve(source, sink);

    println!("{flow}");
}

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

pub struct MaxFlow {
    g: Vec<Vec<Edge>>,
}

impl MaxFlow {
    pub fn add_edge(&mut self, x: usize, y: usize, cap: u64) {
        let i = self.g[x].len();
        let j = self.g[y].len();
        self.g[x].push(Edge {
            tar: y,
            cap,
            rev: j,
        });
        self.g[y].push(Edge {
            tar: x,
            cap: 0,
            rev: i,
        });
    }
    pub fn solve(&mut self, source: usize, sink: usize) -> u64 {
        let n = self.g.len();
        let mut result = 0;
        loop {
            let mut level = vec![usize::MAX; n];
            bfs(source, &mut level, &self.g);
            if level[sink] == usize::MAX {
                return result;
            }
            let mut used = vec![false; n];
            while {
                let f = dfs(u64::MAX, source, sink, &mut used, &mut level, &mut self.g);
                result += f;
                f != 0
            } {}
        }
    }
}

fn bfs(source: usize, level: &mut [usize], g: &[Vec<Edge>]) {
    let mut queue = VecDeque::from([source]);
    level[source] = 0;
    while let Some(x) = queue.pop_front() {
        for &e in &g[x] {
            let y = e.tar;
            if e.cap == 0 || level[y] != usize::MAX {
                continue;
            }
            queue.push_back(y);
            level[y] = level[x] + 1;
        }
    }
}

fn dfs(
    f: u64,
    x: usize,
    sink: usize,
    used: &mut [bool],
    level: &mut [usize],
    g: &mut [Vec<Edge>],
) -> u64 {
    if x == sink {
        return f;
    }
    used[x] = true;
    for i in 0..g[x].len() {
        let e = g[x][i];
        let y = g[x][i].tar;
        let j = g[x][i].rev;
        if used[y] || e.cap == 0 || level[x] >= level[y] {
            continue;
        }
        let f = dfs(f.min(e.cap), y, sink, used, level, g);
        if f > 0 {
            g[x][i].cap -= f;
            g[y][j].cap += f;
            return f;
        }
    }
    level[x] = usize::MAX;
    0
}

#[derive(Clone, Copy, Debug)]
struct Edge {
    tar: usize,
    cap: u64,
    rev: usize,
}