#1175098 (Rust) No.177 制作進行の宮森あおいです！

• 問題: No.177 制作進行の宮森あおいです！
• ユーザー: ngtkana
• 提出日時: 2026-08-06 02:52:56
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 5,014 bytes
• コンパイル時間: 18,091 ms
• コンパイル使用メモリ: 201,640 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-06 02:53:17
• 合計ジャッジ時間: 14,821 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 13

ソースコード

use std::collections::HashSet;

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

fn main() {
    input! {
        required: u64,
        left_len: usize,
        a: [u64; left_len],
        right_len: usize,
        b: [u64; right_len],
    }
    let mut counter = 0..;
    let left = vec_from_fn(left_len, |_| counter.next().unwrap());
    let right = vec_from_fn(right_len, |_| counter.next().unwrap());
    let source = counter.next().unwrap();
    let sink = counter.next().unwrap();

    let mut inst = MaxFlow::new();
    for (i, &a) in a.iter().enumerate() {
        inst.add_edge(source, left[i], a);
    }
    for (j, &b) in b.iter().enumerate() {
        inst.add_edge(right[j], sink, b);
    }
    for j in 0..right_len {
        input! {
            k: usize,
            skip: [Usize1; k],
        }
        let skip = skip.into_iter().collect::<HashSet<_>>();
        for i in 0..left_len {
            if !skip.contains(&i) {
                inst.add_edge(left[i], right[j], u64::MAX);
            }
        }
    }
    let (flow, _cut) = inst.solve(counter.start, source, sink);
    let ans = flow >= required;
    println!("{}", if ans { "SHIROBAKO" } else { "BANSAKUTSUKITA" });
}

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,
    }
}
// }}}