Submission #65068712

---

Source Code Expand

"""
<方針>
- `M` も `N` も大きいので、`O(MN)` は無理なので、毎回料理を見る余裕は当然ない。
- それぞれの料理がいつから `D` 食べれるようになるかを予め調べれば良い。
"""
# 入力
N, M = map(int, input().split())
AA = []
for _ in range(M):
  K, *A = map(int, input().split())
  A = [a-1 for a in A]
  AA.append(A)
B = list(map(int, input().split()))
B = [b-1 for b in B]

# B の index と value を入れ替える。
indB = [None]*N
for i, b in enumerate(B):
  indB[b] = i

# 初めて料理を食べれるようになる日
D = [0]*N

# 料理を順番に調べる
for A in AA:
  # 食材を克服する日
  invA = [None]*len(A)
  for i, a in enumerate(A):
    invA[i] = indB[a]
  # 最後の食材を克服する日が初めてその料理を食べれるようになる日
  D[max(invA)] += 1

# 答え。食べれるものは累積和的に増えて行く。
ans = 0
for d in D:
  ans += d
  print(ans)

Submission Info

Judge Result