結果
問題 |
No.679 不思議マーケット
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:58:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 2,392 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 81,660 KB |
実行使用メモリ | 74,220 KB |
最終ジャッジ日時 | 2025-06-12 20:00:55 |
合計ジャッジ時間 | 1,797 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
import sys from collections import deque def main(): n, m = map(int, sys.stdin.readline().split()) must = set() g_list = [] for _ in range(m): parts = sys.stdin.readline().split() g = int(parts[0]) r = int(parts[1]) h = list(map(int, sys.stdin.readline().split())) g_list.append((g, h)) # 确定必须拿走的商品 all_g = set(g for g, h in g_list) must = set() for num in range(1, n+1): if num not in all_g: must.add(num) count_must = len(must) # 初始化类型A typeA = set() queue = deque() for g, h in g_list: flag = True for hj in h: if hj not in must and hj not in typeA: flag = False break if flag: typeA.add(g) queue.append(g) # 迭代更新类型A while queue: g = queue.popleft() for idx in range(m): gg, hh = g_list[idx] if gg in typeA: continue flag = True for hj in hh: if hj not in must and hj not in typeA: flag = False break if flag: if gg not in typeA: typeA.add(gg) queue.append(gg) # 确定类型B typeB = [] for g, h in g_list: if g not in typeA: typeB.append(g) # 构造依赖关系图 adj = {} in_degree = {} for g in typeB: adj[g] = [] in_degree[g] = 0 for g, h_list in g_list: if g not in typeB: continue for hj in h_list: if hj in typeB: adj[hj].append(g) in_degree[g] += 1 # 拓扑排序计算最长路径 max_len = {g: 0 for g in typeB} queue = deque() for g in typeB: if in_degree[g] == 0: queue.append(g) while queue: u = queue.popleft() for v in adj[u]: if max_len[v] < max_len[u] + 1: max_len[v] = max_len[u] + 1 in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) count_B_max = max(max_len.values()) if typeB else 0 total = count_must + len(typeA) + count_B_max print(total) if __name__ == "__main__": main()