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

• 問題: No.177 制作進行の宮森あおいです！
• ユーザー: cologne
• 提出日時: 2026-02-11 14:11:44
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 9,000 bytes
• コンパイル時間: 2,724 ms
• コンパイル使用メモリ: 224,968 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-02-11 14:11:49
• 合計ジャッジ時間: 4,715 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

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

コンパイルメッセージ

warning: unused import: `std::cmp::Reverse`
 --> src/main.rs:2:5
  |
2 | use std::cmp::Reverse;
  |     ^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: associated function `max_value` is never used
  --> src/main.rs:23:12
   |
 7 |     pub trait Integral:
   |               -------- associated function in this trait
...
23 |         fn max_value() -> Self;
   |            ^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: field `lim` is never read
  --> src/main.rs:43:9
   |
39 |     struct FlowCalc<'a, Cap: Integral> {
   |            -------- field in this struct
...
43 |         lim: Cap,
   |         ^^^

warning: struct `Edge` is never constructed
   --> src/main.rs:115:16
    |
115 |     pub struct Edge<Cap: Integral> {
    |                ^^^^

warning: methods `get_edge`, `change_edge`, and `flow` are never used
   --> src/main.rs:149:16
    |
122 |     impl<Cap: Integral> Maxflow<Cap> {
    |     -------------------------------- methods in this implementation
...
149 |         pub fn get_edge(&mut self, i: usize) -> Edge<Cap> {
    |                ^^^^^^^^
...
161 |         pub fn change_edge(&mut self, i: usize, new_cap: Cap, new_flow: Cap) {
    |                ^^^^^^^^^^^
...
170 |         pub fn flow(&mut self, s: usize, t: usize) -> Cap {
    |                ^^^^

ソースコード

use fio::*;
use std::cmp::Reverse;

mod flow {
    use std::collections::VecDeque;
    use std::ops::{Add, AddAssign, Sub, SubAssign};
    pub trait Integral:
        'static
        + Send
        + Sync
        + Copy
        + Clone
        + Ord
        + Add<Output = Self>
        + Sub<Output = Self>
        + AddAssign
        + SubAssign
    {
        /// Returns 0.
        fn zero() -> Self;

        /// Returns maximum value representable in type.
        fn max_value() -> Self;
    }
    macro_rules! integral_impl {
        ($($SelfT:ty)*) => {
            $(impl Integral for $SelfT {
                fn zero() -> Self {
                    0
                }
                fn max_value() -> Self {
                    Self::MAX
                }
            })*
        }
    }
    integral_impl!(i8 i16 i32 i64 u8 u16 u32 u64 usize isize);

    struct FlowCalc<'a, Cap: Integral> {
        g: &'a mut Maxflow<Cap>,
        s: usize,
        t: usize,
        lim: Cap,
        lev: Vec<i32>,
        it: Vec<usize>,
        q: VecDeque<usize>,
    }
    impl<Cap: Integral> FlowCalc<'_, Cap> {
        fn bfs(&mut self) {
            self.lev.fill(-1);
            self.lev[self.s] = 0;
            self.q.clear();
            self.q.push_back(self.s);
            while let Some(v) = self.q.pop_front() {
                for e in &self.g.g[v] {
                    if e.cap == Cap::zero() || self.lev[e.to] != -1 {
                        continue;
                    }
                    self.lev[e.to] = self.lev[v] + 1;
                    if e.to == self.t {
                        return;
                    }
                    self.q.push_back(e.to);
                }
            }
        }
        fn dfs(&mut self, v: usize, f: Cap) -> Cap {
            if v == self.s {
                return f;
            }
            let mut r = Cap::zero();
            let prv_lv = self.lev[v] - 1;
            for i in self.it[v]..self.g.g[v].len() {
                self.it[v] = i;
                let _Edg {
                    to: e_to,
                    rev: e_rev,
                    ..
                } = self.g.g[v][i];
                if prv_lv != self.lev[e_to] || self.g.g[e_to][e_rev].cap == Cap::zero() {
                    continue;
                }
                let d = self.dfs(e_to, self.g.g[e_to][e_rev].cap.min(f - r));
                if d == Cap::zero() {
                    continue;
                }
                self.g.g[v][i].cap += d;
                self.g.g[e_to][e_rev].cap -= d;
                r += d;
                if r == f {
                    return r;
                }
            }
            self.it[v] = self.g.g[v].len();
            r
        }
    }

    pub struct Maxflow<Cap: Integral> {
        n: usize,
        /// i'th edge: g[.0][.1]
        e_pos: Vec<(usize, usize)>,
        g: Vec<Vec<_Edg<Cap>>>,
    }

    /// g[g[i][j].to][g[i][j].rev] = i
    #[derive(Clone, Debug)]
    struct _Edg<Cap: Integral> {
        to: usize,
        rev: usize,
        cap: Cap,
    }

    #[derive(Clone, Debug)]
    pub struct Edge<Cap: Integral> {
        pub from: usize,
        pub to: usize,
        pub cap: Cap,
        pub flow: Cap,
    }

    impl<Cap: Integral> Maxflow<Cap> {
        pub fn new(n: usize) -> Self {
            Self {
                n,
                e_pos: vec![],
                g: vec![vec![]; n],
            }
        }

        /// Add an edge from -> to with capacity cap. Returns an index of edge.
        pub fn add_edge(&mut self, from: usize, to: usize, cap: Cap) -> usize {
            assert!(from < self.n);
            assert!(to < self.n);
            assert!(Cap::zero() <= cap);
            let m = self.e_pos.len();
            self.e_pos.push((from, self.g[from].len()));
            let rev = self.g[to].len() + if from == to { 1 } else { 0 };
            self.g[from].push(_Edg { to, rev, cap });
            let rev = self.g[from].len() - 1;
            self.g[to].push(_Edg {
                to: from,
                rev,
                cap: Cap::zero(),
            });
            m
        }

        pub fn get_edge(&mut self, i: usize) -> Edge<Cap> {
            assert!(i < self.e_pos.len());
            let e = &self.g[self.e_pos[i].0][self.e_pos[i].1];
            let r = &self.g[e.to][e.rev];
            Edge {
                from: self.e_pos[i].0,
                to: e.to,
                cap: e.cap + r.cap,
                flow: r.cap,
            }
        }

        pub fn change_edge(&mut self, i: usize, new_cap: Cap, new_flow: Cap) {
            assert!(i < self.e_pos.len());
            assert!((Cap::zero()..=new_cap).contains(&new_flow));
            let e = &mut self.g[self.e_pos[i].0][self.e_pos[i].1];
            e.cap = new_cap - new_flow;
            let (to, rev) = (e.to, e.rev);
            self.g[to][rev].cap = new_flow;
        }

        pub fn flow(&mut self, s: usize, t: usize) -> Cap {
            self.flow_with_capacity(s, t, Cap::max_value())
        }

        pub fn flow_with_capacity(&mut self, s: usize, t: usize, limit: Cap) -> Cap {
            let n = self.n;
            assert!(s < n);
            assert!(t < n);
            assert_ne!(s, t);
            assert!(Cap::zero() <= limit);

            let mut calc = FlowCalc {
                g: self,
                s,
                t,
                lim: limit,
                lev: vec![0; n],
                it: vec![0; n],
                q: VecDeque::new(),
            };

            let mut r = Cap::zero();
            while r < limit {
                calc.bfs();
                if calc.lev[t] == -1 {
                    break;
                }
                calc.it.fill(0);
                r += calc.dfs(t, limit - r);
            }
            r
        }
    }
}

use flow::*;

fn main() {
    let w = read::<u16>();
    let n = read::<usize>();
    let j = read_vec::<u16>();
    let m = read::<usize>();
    let c = read_vec::<u16>();

    let mut g = Maxflow::<u16>::new(n + m + 2);
    let source = n + m;
    let sink = n + m + 1;
    for (i, v) in j.into_iter().enumerate() {
        g.add_edge(source, i, v);
    }
    for (i, v) in c.into_iter().enumerate() {
        g.add_edge(n + i, sink, v);
    }
    for i in 0..m {
        let qs = read_vec::<usize>();
        let qs = qs.into_iter().skip(1).map(|x| x - 1).collect::<Vec<_>>();
        if let Some(lst) = qs.last() {
            for j in 0..qs[0] {
                g.add_edge(j, n + i, u16::MAX);
            }
            for w in qs.windows(2) {
                for j in w[0] + 1..w[1] {
                    g.add_edge(j, n + i, u16::MAX);
                }
            }
            for j in lst + 1..n {
                g.add_edge(j, n + i, u16::MAX);
            }
        } else {
            for j in 0..n {
                g.add_edge(j, n + i, u16::MAX);
            }
        }
    }
    println!(
        "{}",
        if w == g.flow_with_capacity(source, sink, w) {
            "SHIROBAKO"
        } else {
            "BANSAKUTSUKITA"
        }
    );
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}