結果

問題 No.30 たこやき工場
ユーザー むらためむらため
提出日時 2018-12-16 03:17:46
言語 Nim
(2.0.2)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,600 bytes
コンパイル時間 3,738 ms
コンパイル使用メモリ 69,992 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-01 03:02:44
合計ジャッジ時間 4,283 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
/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