結果
問題 | No.679 不思議マーケット |
ユーザー |
|
提出日時 | 2019-01-28 01:12:54 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 996 bytes |
コンパイル時間 | 2,659 ms |
コンパイル使用メモリ | 63,648 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 11:03:28 |
合計ジャッジ時間 | 3,275 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
import sequtils template times*(n:int,body) = (for _ in 0..<n: body) proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': break result = 10 * result + k.ord - '0'.ord proc topologicalSort(E:seq[seq[int]]) : seq[int] = # E : [n->[m1,m2,m3], ... ]の隣接リスト を ソート var visited = newSeq[bool](E.len) var answer = newSeq[int]() proc visit(src:int) = if visited[src] : return visited[src] = true for dst in E[src]: visit(dst) answer &= src # 葉から順に追加される for src in 0..<E.len: visit(src) return answer let n = scan() let m = scan() var E = newSeqWith(n+1,newSeq[int]()) m.times: let g = scan() let r = scan() r.times: E[g] &= scan() var bought = newSeq[bool](n+1) var ans = 0 for e in E.topologicalSort(): if e == 0 : continue if E[e].len == 0 or E[e].allIt(bought[it]): ans += 1 bought[e] = true echo ans