結果

問題 No.30 たこやき工場
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:36:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 54 ms / 5,000 ms
コード長 2,374 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 67,048 KB
最終ジャッジ日時 2025-03-31 17:36:58
合計ジャッジ時間 1,593 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict, deque

def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())

    manufacture = defaultdict(list)  # R -> list of (P, Q)
    dependencies = defaultdict(list)  # adjacency list for the graph. p → r edges.
    indegree = [0] * (n + 1)  # 1-based indexing

    for _ in range(m):
        p, q, r = map(int, sys.stdin.readline().split())
        manufacture[r].append((p, q))
        dependencies[p].append(r)  # p is needed for r, so edge p → r
        indegree[r] += 1  # increment in-degree of r

    # Compute topological order
    queue = deque()
    topo_order = []

    # Initialize queue with nodes having in-degree 0
    for node in range(1, n + 1):
        if indegree[node] == 0:
            queue.append(node)

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in dependencies[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    # Process in reverse topological order
    reversed_order = reversed(topo_order)
    required = [0] * (n + 1)
    required[n] = 1  # need to produce 1 of product N

    S = [0] * (n - 1)  # S[0] is product 1, ..., S[n-2] is product N-1

    for i in reversed_order:
        if i in manufacture:
            for (p, q) in manufacture[i]:
                required[p] += required[i] * q
        if i < n:
            # Check if the product has manufacturing methods. If not, add to S.
            # If it has manufacturing methods, then it's processed in the above loop.
            # So, we need to check if i has any manufacturing methods.
            if i not in manufacture:
                S[i - 1] += required[i]

    # For products that have manufacturing methods, their required is already propagated.
    # So, S[i-1] should be 0 if they have any manufacture.
    # However, for products with manufacture, their required is propagated, so their own required[i] is not part of S.
    # So, the code above adds to S only if i is in 1..N-1 and not in manufacture.

    # Now, for products that are in manufacture but their required is calculated via dependencies,
    # The required[i] is already propagated to their materials. So, those products are considered as manufactured, not bought.

    for val in S:
        print(val)

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