Submission #40867855

---

Source Code Expand

when NimMajor <= 0 and NimMinor <= 18: import future else: import sugar

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
when defined release: {.checks: off.}

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from typetraits import arity
from sequtils import map, mapIt, newSeqWith, toSeq
from strutils import split, parseInt, parseFloat, parseBool, parseEnum, parseBiggestInt
when NimMajor == 0 and NimMinor >= 14: from strutils import parseBiggestUInt

import macros

from terminal import setForegroundColor, ForegroundColor, resetAttributes
proc warn(message: string) =
  when not defined release:
    stderr.setForegroundColor(fgYellow)
    stderr.write("注意: ")
    stderr.resetAttributes
    stderr.writeLine message

when not declared parseBiggestUInt:
  proc parseBiggestUInt(s: string): uint64 = uint64(parseInt(s))
when not declared SomeFloat:
  type SomeFloat = float | float64 | float32
when not defined nimHasRunnableExamples:
  template runnableExamples*(body: untyped) = discard

proc parseT(s: string; T: typedesc): auto =
  ## `parse` 系関数のジェネリック版
  ## `T` が `SomeOrdinal | SomeFloat` (subranges を含む) でない場合，そのまま `s` を返す
  runnableExamples:
    doAssert parseT("12", int) == 12
    doAssert parseT("12", uint) == 12
    doAssert parseT("12", int64) == 12
    doAssert parseT("12", float32) == 12.0
    doAssert parseT("Yes", bool) == true

  when T is SomeSignedInt: cast[T](parseBiggestInt(s))
  elif T is SomeUnsignedInt: cast[T](parseBiggestUInt(s))
  elif T is SomeFloat: cast[T](parseFloat(s))
  elif T is enum: parseEnum[T](s)
  elif T is bool: parseBool(s)
  elif T is char: s[0]
  else: s

proc unpackWithParse*(input: openArray[string]; T: typedesc[tuple]): T =
  ## 文字列配列を `T` で指定された `tuple` に `parse` しながら変換する
  runnableExamples:
    let t = unpackWithParse(@["1", "1", "1", "1", "1"], 4, tuple[a: int8, b: uint32, c: float64, d: bool])
    doAssert int8 is t.a.type and t.a == 1
    doAssert uint32 is t.b.type and t.b == 1
    doAssert float64 is t.c.type and t.c == 1.0
    doAssert bool is t.d.type and t.d == true
    doAssert tuple[a: int8, b: uint32, c: float64, d: bool] is t.type

  var i = 0
  for x in result.fields:
    if i > input.high:
      warn "元の配列の長さが " & $T.arity & " 未満だから，一部デフォルト値になってるよ"
      break
    x = parseT(input[i], x.type)
    i.inc
  result

proc input(T: typedesc[string]): string = stdin.readLine
proc input(T: typedesc[SomeOrdinal | SomeFloat | char]): auto = input(string).parseT(T)
proc input(T: typedesc[seq[string]]): auto = input(string).split
proc input(T: typedesc[seq[char]]): auto = toSeq(input(string).items)
proc input[E: SomeOrdinal | SomeFloat](T: typedesc[seq[E]]): auto = input(seq[string]).mapIt(it.parseT(E.type))
proc input(T: typedesc[tuple]): auto = input(seq[string]).unpackWithParse(T)

proc toTupleType(parTuple: NimNode): NimNode {.compileTime.} =
  ## `nnkPar` で表現されてる名前付きタプルを `tuple[]` 形式に変換する
  ## `nnkPar` が名前付きタプルじゃない場合は，そのまま返す
  runnableExamples:
    static:
      doAssert((quote do: (a: int, b: float)).toTupleType == (quote do: tuple[a: int, b: float]))
      doAssert((quote do: (a, b: int)).toTupleType == (quote do: tuple[a, b: int]))
      doAssert((quote do: (int, int)).toTupleType == (quote do: (int, int)))
      doAssert((quote do: ()).toTupleType == (quote do: ()))

  if parTuple.len == 0 or parTuple.findChild(it.kind == nnkExprColonExpr) == nil: # () or (T, U, ...)
    result = parTuple
  else:
    result = newTree(nnkTupleTy)
    var identDefs = newTree(nnkIdentDefs)
    for field in parTuple:
      if field.kind == nnkIdent: # (a, b, ..., x: T)  の a, b, ... 部分 (x 以外)
        identDefs.add(field)
      field.copyChildrenTo(identDefs)
      if field.kind != nnkIdent: # (..., x: T, y: ...) の x: T 部分
        identDefs.add(newEmptyNode())
        result.add(identDefs)
        identDefs = newTree(nnkIdentDefs)

proc seqInputCall(bracketTree: NimNode): NimNode {.compileTime.} =
  ## `seq[N, seq[M, ..., [seq[T]]...]]` を `newSeqWith(N, newSeqWith(M, ..., input(seq[T])...))` にする

  if bracketTree.kind != nnkBracketExpr:
    case bracketTree.kind:
      of nnkPar: # x: (Field0: ...)
        result = newCall("input", bracketTree.toTupleType)
      else: # x: T
        result = newCall("input", bracketTree)
  else:
    case bracketTree.len:
      of 2: # seq[N, ... seq[T] ...] の seq[T]
        if bracketTree[^1].kind == nnkBracketExpr:
          error("seq[seq[T]] みたいな書き方はできないって言ったでしょ！ seq[N, seq[T]] みたいに書き直してっ")
        result = newCall("input", bracketTree)
      of 3: # それ以外 (seq[N, ...])
        result = newCall("newSeqWith", bracketTree[1], seqInputCall(bracketTree[^1]))
      else:
        error("変な入力があるよ")

proc appendedProcCallBlocks(procCalls: NimNode; i: int): NimNode =
  ## `procCalls[i]` の関数呼び出しを
  ## .. code-block:: Nim
  ##   block:
  ##     var it = procCall(...)
  ## という形に変換しながらつなげていく
  ## 最後だけは
  ## .. code-block:: Nim
  ##   block:
  ##     var it = lastProcCall(...)
  ##     it
  ## というようにして `it` を返すようにする

  let it = ident("it")
  let procCall = procCalls[i]
  result = newStmtList(quote do:
    var `it` = `procCall`
  )
  if i == procCalls.len - 1: # 最後の要素だけは it を返すようにする
    result.add(it)
  else:
    result.add(appendedProcCallBlocks(procCalls, i + 1))
  result = newBlockStmt(result)

proc inputsImpl(pre, post: NimNode): NimNode {.compileTime.} =
  ## pre で指定された変数に post の結果を入れる

  # input() 部分の生成
  var inputCall: NimNode
  case pre.kind:
    of nnkPar: # (x, y, ...): ...
      result = newTree(nnkVarTuple)
      pre.copyChildrenTo(result)
      result.add(newEmptyNode())
      case post[0].kind:
        of nnkPar: # (x, y, ...): (T, T, ...)
          inputCall = newCall("input", post[0].toTupleType)
        of nnkTupleTy: # (x, y, ...): tuple[Field0: ...]
          inputCall = newCall("input", post)
        else: # (x, y, ...): T
          var parTupleTy = newTree(nnkPar)
          for _ in 0..<pre.len: parTupleTy.add(post[0]) # (int, int, int, ...) みたいなのを作ってる
          inputCall = newCall("input", parTupleTy)
    else: # x: ...
      result = newTree(nnkIdentDefs).add(pre).add(newEmptyNode())
      case post[0].kind:
        of nnkPar: # x: (Field0: ...)
          inputCall = newCall("input", post[0].toTupleType)
        of nnkBracketExpr:
          inputCall = seqInputCall(post[0])
        else: # x: T
          inputCall = newCall("input", post[0])

  # 関数部分の生成（ある場合）と結合
  if post.len > 1:
    let it = ident("it")
    var itStmts = when NimMajor == 0 and NimMinor < 17: newStmtList(quote do: (var `it` = `inputCall`)) # 入力の読み込み
                  else: newStmtList(quote do: (var `it` {.used.} = `inputCall`))
    itStmts.add(appendedProcCallBlocks(post, 1)) # 関数の適用
    result.add(newTree(nnkStmtListExpr, newBlockStmt(itStmts))) # 結合
  else:
    result.add(inputCall) # 結合

macro inputs*(body: untyped): untyped =
  ## 入力を受け取る
  ## 宣言の後に `it` を用いた式を（`y` みたいに用いなくてもいいんだけど）いくつでもかくことができ，
  ## その返り値が変数の値となる
  ## 式中で型が変わってもいい（下の例の `u`, `y` とか見たいな感じ）
  ##
  ## .. code-block:: Nim
  ##   inputs:
  ##     a: int
  ##     b: string
  ##     c: (x: char, y: float)
  ##     d: tuple[x: char, y: float]
  ##     e: (u, v: BiggestInt)
  ##     f: tuple[u, v: int]
  ##     g: seq[int]
  ##     h: seq[a, seq[int]]
  ##     i: seq[a, (s, t: int)]
  ##     (j, k, l): int
  ##     (m, n): (char, float)
  ##     o: seq[a, string]
  ##     (p): int
  ##     q: seq[int]; it.sorted(system.cmp)
  ##     r: seq[float]; it.sorted(cmp).filterIt(it > 0)
  ##     s: seq[char]
  ##     t: seq[2, seq[a, int]]
  ##     u: string; parseInt(it); abs(-it)
  ##     (_, v): (a: char, b: char)
  ##     (w, x): tuple[a, b: char]
  ##     y: int; "hoge"

  expectKind(body, nnkStmtList)
  result = newTree(nnkStmtList)
  var letSection = newTree(nnkLetSection)
  for decl in body:
    case decl[0].kind:
      of nnkIdent: # x: ...
        letSection.add(inputsImpl(decl[0], decl[1]))
      of nnkPar:
        expectMinLen(decl[0], 1)
        if decl[0].len == 1: # (x): ... これは x: ... と同じ扱いにしたい
          letSection.add(inputsImpl(decl[0][0], decl[1]))
        else: # (x, y, ...): ...
          letSection.add(inputsImpl(decl[0], decl[1]))
      else:
        expectKind(decl[0], {nnkIdent, nnkPar})

  result.add(letSection)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc `ceilDiv`*[T](x, y: T): T = x div y + ord(x mod y != 0)
proc `//=`*(x: var SomeInteger; y: SomeInteger) = x = x div y
proc `%=`*(x: var SomeInteger; y: SomeInteger) = x = x mod y
template `<?=`*[T](x: var T; y: T) = x = min(x, y)
template `>?=`*[T](x: var T; y: T) = x = max(x, y)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc withIndex*[T](s: openArray[T]): seq[tuple[i: int, v: T]] =
  (0..s.high).mapIt((it, s[it]))

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
template countIt*[T](a: openArray[T]; pred: untyped): int =
  var result = 0
  for it {.inject.} in items(a):
    if pred: result.inc
  result

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc reversed*(s: string): string =
  result = newString(s.len)
  for i, c in s: result[s.len - i - 1] = c

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import newSeqWith, allIt

template newSeqWithImpl[T](lens: seq[int]; init: T; currentDimension, lensLen: static[int]): untyped =
  when currentDimension == lensLen:
    newSeqWith(lens[currentDimension - 1], init)
  else:
    newSeqWith(lens[currentDimension - 1], newSeqWithImpl(lens, init, currentDimension + 1, lensLen))

template newSeqWith*[T](lens: varargs[int]; init: T): untyped =
  assert(lens.allIt(it > 0))
  newSeqWithImpl(@lens, init, 1, lens.len)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
when not defined(release):
  template stderrEcho*(x: varargs[string, `$`]) =
    for v in x:
      stderr.write(v)
    stderr.writeLine ""

  template stderrEcho*[T](x: seq[seq[T]]) =
    for v in x: stderrEcho v

  template stderrEcho*(x: seq[string]) =
    for v in x: stderrEcho v
else:
  template stderrEcho*(x: untyped) = discard

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from std/os import relativePath, getCurrentDir

proc discardableId[T](x: T): T {.discardable.} = x

template dbg*(exprs: varargs[untyped]): untyped =
  let result = (exprs)
  when not defined(release):
    let info = instantiationInfo(fullPaths = true)
    stderr.write "[", os.relativePath(info.filename, os.getCurrentDir()), ":", $info.line, "] "
    stderr.writeLine (exprs).astToStr, " = ", result
  discardableId(result)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from algorithm import SortOrder

# デフォルトは min-heap （最小要素が pop される）
# デフォルトとは cmp(x, y) = (if x < y: -1 elif x == y: 0 else: 1) かつ order = Ascending な状態）
type
  BinaryHeap*[T] = object
    nodes: seq[T]
    cmp: proc (x, y: T): int
    popChunk: bool
  BinaryHeapRef*[T] = ref BinaryHeap[T]
  BinaryHeapTypes[T] = BinaryHeap[T] | BinaryHeapRef[T]

# 初期化
proc initBinaryHeap*[T](cmp: proc(x, y: T): int {.closure.}; order: SortOrder = Ascending): BinaryHeap[T] =
  if order == Ascending: BinaryHeap[T](nodes: newSeq[T](), cmp: cmp, popChunk: false)
  else: BinaryHeap[T](nodes: newSeq[T](), cmp: proc (x, y: T): int = cmp(y, x), popChunk: false)
proc initBinaryHeap*[T](order: SortOrder = Ascending): BinaryHeap[T] = initBinaryHeap[T](cmp, order)
proc newBinaryHeap*[T](cmp: proc(x, y: T): int {.closure.}; order: SortOrder = Ascending): BinaryHeapRef[T] =
  if order == Ascending: BinaryHeapRef[T](nodes: newSeq[T](), cmp: cmp, popChunk: false)
  else: BinaryHeapRef[T](nodes: newSeq[T](), cmp: proc (x, y: T): int = cmp(y, x), popChunk: false)
proc newBinaryHeap*[T](order: SortOrder = Ascending): BinaryHeapRef[T] = newBinaryHeap[T](cmp, order)

# TODO: 引数
proc toBinaryHeap*[T](a: seq[T]; cmp: proc(x, y: T): int {.closure.}; order: SortOrder = Ascending): BinaryHeap[T] =
  result = initBinaryHeap[T](cmp, order)
  result.nodes = a
  for i in countdown(a.len shr 1 - 1, 0):
    result.siftDown(i)
proc toBinaryHeap*[T](a: seq[T]; order: SortOrder = Ascending): BinaryHeap[T] = a.toBinaryHeap(cmp[T], order)

# 直接構築？
# TODO: いい感じにする
proc add*[T](self: var BinaryHeapTypes[T]; node: T) = # TODO: proc名改善
  ## これは，ヒープの順序が正しくなるように挿入されることを保証しない
  ## 正しく挿入したいときは push を使うこと
  self.nodes.add(node)
proc heapify*[T](self: var BinaryHeapTypes[T]) =
  for i in countdown(self.len shr 1 - 1, 0):
    self.siftDown(i)

# impls
proc siftDown[T](self: var BinaryHeapTypes[T]; index: SomeInteger) {.inline.} =
  ## 根->葉 方向に nodes[index] とその子ノードたちを整形

  self.popChunk = false
  let len = self.nodes.len
  let item = self.nodes[index]
  var parent = index
  var child = parent shl 1 + 1
  while child < len:
    let right = child + 1
    if right < len and self.cmp(self.nodes[child], self.nodes[right]) >= 0: child = right
    self.nodes[parent] = self.nodes[child]
    parent = child
    child = child shl 1 + 1
  self.nodes[parent] = item
  self.siftUp(index, parent)

proc siftUp[T](self: var BinaryHeapTypes[T]; rootIndex, nodeIndex: SomeInteger) {.inline.} =
  let node = self.nodes[nodeIndex]
  var child = nodeIndex
  while child > rootIndex:
    let parent = (child - 1) shr 1
    if self.cmp(self.nodes[parent], node) <= 0: break
    self.nodes[child] = self.nodes[parent]
    child = parent
  self.nodes[child] = node

proc pushImpl[T](self: var BinaryHeapTypes[T]; node: T) {.inline.} =
  self.nodes.add(node)
  self.siftUp(0, self.nodes.len - 1)

proc popImpl[T](self: var BinaryHeapTypes[T]): T {.inline.} =
  ## > 「pop された要素を穴とすると，その穴の左右の子を見て条件に合うほうを親にする操作を繰り返して，
  ## > 穴を葉の部分にまで持ってきた後，穴と葉の一番端（self.nodes[^1]の要素）を入れ替えて，
  ## > 入れ替えた要素を適切な位置まで持ってくる
  ## > N を要素数として siftDown は 2*log(N) 回の比較が必要だけど，
  ## > この方法なら log(N) 回 + siftUp にかかる回数になって，
  ## > 葉要素がそんなにたくさん siftUp されることはないと思うから，ちょっとマシになりそう」
  ## らしい (https://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heaps)

  result = self.nodes[0]
  let len = self.nodes.len
  var parent = 0
  var child = 1
  while child < len:
    let right = child + 1
    if right < len and self.cmp(self.nodes[child], self.nodes[right]) > 0: child = right
    self.nodes[parent] = self.nodes[child]
    parent = child
    child = child shl 1 + 1
  self.nodes.del(parent) # 穴と末尾の要素を交換しつつ，穴を削除
  if parent < len - 1:
    self.siftUp(0, parent) # 交換した要素を正しい位置に移動

# 操作
proc top*[T](self: var BinaryHeapTypes[T]): T =
  if self.popChunk: discard self.popImpl()
  self.popChunk = false
  return self.nodes[0]
proc pop*[T](self: var BinaryHeapTypes[T]): T =
  result = self.top
  self.popChunk = true
proc push*[T](self: var BinaryHeapTypes[T]; node: T) =
  if self.popChunk:
    self.nodes[0] = node
    self.siftDown(0)
  else:
    self.pushImpl(node)

# その他
proc len*[T](self: BinaryHeapTypes[T]): int = self.nodes.len - self.popChunk.ord

proc toSeq*[T](self: var BinaryHeapTypes[T]): seq[T] =
  if self.popChunk: discard self.popImpl()
  return self.nodes
iterator items*[T](self: BinaryHeapTypes[T]): T =
  var heap = self
  if heap.popChunk: discard heap.popImpl()
  for node in heap.nodes: yield node

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import newSeqWith
from algorithm import fill, reversed

const inf = int.high div 10

type
  Edge* = tuple[to, cost: int]

type Dijkstra = ref object of RootObj
  G: seq[seq[Edge]] # グラフ (addEdge で辺を追加していく)
  dists: seq[int] # start から各ノードへの最短距離
  prev: seq[int] # 経路復元用
  s: int

proc newDijkstra*(V: int): Dijkstra =
  result = Dijkstra(G: newSeqWith(V, newSeq[Edge]()), dists: newSeq[int](V), prev: newSeq[int](V), s: -1)

proc addEdge*(self: var Dijkstra; f, t, c: int#[; counts: var seq[int]]#) =
  # f: from, t: to, c: cap
  self.G[f].add((to: t, cost: c))
  # counts[t].inc

proc calc*(self: var Dijkstra; start: int) =
  self.s = start
  var que = newBinaryHeap[tuple[d, v: int]]()
  que.push((self.dists[start], start))
  self.dists.fill(inf)
  self.dists[start] = 0
  self.prev.fill(-1)

  while que.len > 0:
    let p = que.pop
    for g in self.G[p.v]:
      if self.dists[g.to] > self.dists[p.v] + g.cost:
        self.dists[g.to] = self.dists[p.v] + g.cost
        self.prev[g.to] = p.v
        que.push((self.dists[g.to], g.to))

proc shortestPathLength*(self: Dijkstra; terminal: int): int =
  assert self.s in self.dists.low..self.dists.high, "calc() を呼んでないよ"
  return self.dists[terminal]

proc shortestPath*(self: Dijkstra; terminal: int): seq[int] =
  assert self.s in self.dists.low..self.dists.high, "calc() を呼んでないよ"
  result = newSeq[int]()
  var t = terminal
  while t != self.s:
    result.add(t)
    t = self.prev[t]
  result.add(self.s)
  return result.reversed

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from strutils import join

inputs:
  (N, M): int
  graph: seq[M, (int, int)]; it.mapIt((u: it[0].pred, v: it[1].pred))
  K: int
  conds: seq[K, (int, int)]; it.mapIt((p: it[0].pred, d: it[1]))

var D = newSeqWith(N, N, int.high div 2)

var a = newDijkstra(N)
for (u, v) in graph:
  a.addEdge(u, v, 1)
  a.addEdge(v, u, 1)
for i in 0 ..< N:
  a.calc(i)
  for j in 0 ..< N:
    D[i][j] = a.shortestPathLength(j)

var C = newSeqWith(N, 1)
for (p, d) in conds:
  for i in 0 ..< N:
    if D[p][i] < d:
      C[i] = 0
for (p, d) in conds:
  var isOK = false
  for i in 0 ..< N:
    if D[p][i] == d and C[i] == 1:
      isOK = true
  if not isOK:
    echo "No"
    quit()

if 1 in C:
  echo "Yes"
  echo C.join("")
else:
  echo "No"

Submission Info

Compile Error

/imojudge/sandbox/Main.nim(14, 6) Warning: imported and not used: 'terminal' [UnusedImport]

Judge Result