Module c

ABC 402 C - Dislike Foods

refs: https://atcoder.jp/contests/abc402/tasks/abc402_c

N と M の最大値がそれなりに大きいが, K_i の総和がたかだか3 x 10^5. 各 B_i が与えられた際にどの料理についての計算を行えばよいかだけ識別できれば, 十分に間に合う.

use std::collections::HashMap;

use proconio::input;

fn main() {
    input! {
        n: usize, m: usize,
        ka: [[usize]; m],
        b: [usize; n],
    }

    let mut recipe_count = Vec::from_iter(ka.iter().map(|k| k.len()));
    let mut food_map = HashMap::<usize, Vec<usize>>::new();
    for (i, k) in ka.iter().enumerate() {
        for &ki in k.iter() {
            food_map.entry(ki).or_default().push(i);
        }
    }

    let mut ans = 0;
    for &bi in b.iter() {
        let recipes = food_map.entry(bi).or_default();
        for &recipe in recipes.iter() {
            recipe_count[recipe] -= 1;
            if recipe_count[recipe] == 0 {
                ans += 1;
            }
        }

        println!("{ans}");
    }
}