# C - Dislike Foods [문제 링크](https://atcoder.jp/contests/abc402/tasks/abc402_c) ## Problem Statement The AtCoder Restaurant uses $N$ types of ingredients numbered from $1$ to $N$. The restaurant offers $M$ dishes numbered from $1$ to $M$. Dish $i$ uses $K_i$ types of ingredients, namely $A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}$. Snuke currently dislikes all $N$ ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients. Over the next $N$ days, he will overcome his dislikes one ingredient per day. On day $i$, he overcomes ingredient $B_i$, and from then on he no longer dislikes it. For each $i = 1,2,\ldots,N$, find: - the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient $B_i$ on day $i$. ## Constraints - $1 \le N \le 3 \times 10^{5}$ - $1 \le M \le 3 \times 10^{5}$ - $1 \le K_i \le N\ (1 \le i \le M)$ - $\sum K_i \le 3 \times 10^{5}$ - $1 \le A_{i,j} \le N\ (1 \le i \le M,\ 1 \le j \le K_i)$ - $A_{i,j} \ne A_{i,k}\ (1 \le i \le M,\ j \ne k)$ - $1 \le B_i \le N\ (1 \le i \le N)$ - $B_i \ne B_j\ (i \ne j)$ - All input values are integers. ## Input The input is given from Standard Input in the following format: $ N\ M $ $ K_1\ A_{1,1}\ A_{1,2}\ \ldots\ A_{1,K_1} $ $ K_2\ A_{2,1}\ A_{2,2}\ \ldots\ A_{2,K_2} $ $ \vdots $ $ K_M\ A_{M,1}\ A_{M,2}\ \ldots\ A_{M,K_M} $ $ B_1\ B_2\ \ldots\ B_N $ ## Output Print $N$ lines. The $k$-th line should contain the answer for $i = k$. ## 풀이 #### 각각의 재료들이 포함되는 음식들을 저장하고, 새로 먹을 수 있는 재료가 입력으로 들어올 때마다 새로 먹을 수 있는 음식들을 확인해주었다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 300001; bool overcome[MAX]; int food[MAX]; vector<vector<int>> ingredient(MAX); int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i=0;i<m;i++) { cin >> food[i]; for(int j=0;j<food[i];j++) { int A; cin >> A; ingredient[A].push_back(i); } } int cnt=0; while(n--) { int B; cin >> B; if(!overcome[B]) { overcome[B]=true; for(int e:ingredient[B]) { if(--food[e]==0) cnt++; } } cout << cnt << '\n'; } } ```