結果

問題 No.679 不思議マーケット
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:53:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 1,655 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 69,376 KB
最終ジャッジ日時 2025-06-12 14:56:50
合計ジャッジ時間 1,802 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from collections import defaultdict, deque

    n, m = map(int, sys.stdin.readline().split())
    conditions = defaultdict(list)
    required = set()
    no_condition = set(range(1, n+1))

    for _ in range(m):
        parts = sys.stdin.readline().split()
        g = int(parts[0])
        r = int(parts[1])
        h_list = list(map(int, sys.stdin.readline().split()))
        conditions[g] = h_list
        required.add(g)
        no_condition.discard(g)

    # Build the dependency graph
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    all_nodes = set(range(1, n+1))
    for g in conditions:
        for h in conditions[g]:
            graph[h].append(g)
            in_degree[g] += 1

    # Compute the maximum subset that can be topologically sorted
    # Using Kahn's algorithm with possible nodes
    max_order = []
    queue = deque()
    for node in all_nodes:
        if in_degree.get(node, 0) == 0:
            queue.append(node)

    while queue:
        node = queue.popleft()
        max_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # The nodes not in the topological order cannot satisfy all their conditions
    # So we can't include them in the must-buy set
    must_buy = set(max_order)
    can_buy = no_condition - must_buy

    # Also, include any required nodes that are in the must_buy set
    must_buy = must_buy.intersection(required)
    res = len(must_buy) + len(no_condition) + len(can_buy)
    print(res)

if __name__ == '__main__':
    main()
0