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::>(); 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(len: usize, f: impl FnMut(usize) -> T) -> Vec { (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, } 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 { self.edges.iter().step_by(2).copied().collect() } pub fn solve(&mut self, n: usize, source: usize, sink: usize) -> (u64, Vec) { 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::>(); '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, } } // }}}