結果
問題 |
No.30 たこやき工場
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()