結果

問題 No.30 たこやき工場
ユーザー むらため
提出日時 2018-12-16 03:17:46
言語 Nim
(2.2.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,600 bytes
コンパイル時間 4,498 ms
コンパイル使用メモリ 67,840 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-21 05:28:19
合計ジャッジ時間 5,336 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 36) Warning: imported and not used: 'math' [UnusedImport]
/home/judge/data/code/Main.nim(1, 41) Warning: imported and not used: 'sugar' [UnusedImport]
/home/judge/data/code/Main.nim(1, 26) Warning: imported and not used: 'algorithm' [UnusedImport]

ソースコード

diff # 

import sequtils,strutils,algorithm,math,sugar,macros
template get*():string = stdin.readLine().strip()
macro unpack*(arr: auto,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `arr`;())
  for i in 0..<cnt: result[1].add(quote do:`t`[`i`])
template times*(n:int,body:untyped): untyped = (for _ in 0..<n: body)
template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)

let
  N = get().parseInt() # < 100
  M = get().parseInt() # < 1500
  PQR = newSeqWith(M,get().split().map(parseInt)) # P,R<N  Q<100
  # PをQ個でRができる

# 末端ノードがいくら必要か ? && 全て使う :: DAGらしい :: トポロジカルソート :: O(V+E) == O(N+M)
proc topologicalSort(edges:seq[seq[int]]) : seq[int] =
  # edges : n -> m の隣接リスト
  var visited = newSeqWith(edges.len,0)
  var tsorted = newSeq[int]()
  proc visit(node:int) =
    visited[node] += 1
    if visited[node] > 1: return
    for edge in edges[node]: visit(edge)
    tsorted &= node
  for n in 0..<edges.len: # 孤立点除去 ?
    visit(n)
  return tsorted.filterIt(visited[it] > 1 or edges[it].len > 0)

var succEdges = newSeqWith(N+1,newSeq[int]())
var backWords = newSeqWith(N+1,newSeq[tuple[back,cost:int]]())
for pqr in PQR:
  let (p,q,r) = pqr.unpack(3)
  succEdges[p] &= r
  backWords[r] &= (p,q)
let tsorted = topologicalSort(succEdges)
var ans = newSeqWith(N+1,0)
ans[N] = 1
for n in tsorted:
  for bc in backWords[n]:
    let (back,cost) = bc
    ans[back] += ans[n] * cost
for i,n in ans[1..^2]:
  if backWords[i+1].len == 0: echo n
  else: echo 0
0