結果
問題 |
No.679 不思議マーケット
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:58:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 1,302 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 69,040 KB |
最終ジャッジ日時 | 2025-06-12 20:00:50 |
合計ジャッジ時間 | 1,783 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
import sys from collections import deque, defaultdict def main(): input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr += 1 m = int(input[ptr]) ptr += 1 g_i_dict = {} for _ in range(m): g_i = int(input[ptr]) ptr += 1 r_i = int(input[ptr]) ptr += 1 h_list = list(map(int, input[ptr:ptr + r_i])) ptr += r_i g_i_dict[g_i] = h_list.copy() all_products = set(range(1, n + 1)) mandatory_products = all_products - set(g_i_dict.keys()) edges = defaultdict(list) in_degree = defaultdict(int) for g in g_i_dict: in_degree[g] = 0 # Initialize in_degree for all g_i's for g_i in g_i_dict: for h in g_i_dict[g_i]: if h in g_i_dict: edges[h].append(g_i) in_degree[g_i] += 1 queue = deque() for g in g_i_dict: if in_degree[g] == 0: queue.append(g) top_order = [] count = 0 while queue: u = queue.popleft() top_order.append(u) count += 1 for v in edges[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) total = len(mandatory_products) + count print(total) if __name__ == "__main__": main()