結果

問題 No.994 ばらばらコイン
コンテスト
ユーザー chaemon
提出日時 2020-02-21 21:27:41
言語 Nim
(2.2.0)
結果
WA  
実行時間 -
コード長 1,812 bytes
コンパイル時間 3,894 ms
コンパイル使用メモリ 72,064 KB
実行使用メモリ 17,456 KB
最終ジャッジ日時 2024-10-08 21:04:46
合計ジャッジ時間 5,562 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(71, 21) Warning: Using an unnamed break in a block is deprecated; Use a named block with a named break instead [UnnamedBreak]
/home/judge/data/code/Main.nim(2, 57) Warning: imported and not used: 'strutils' [UnusedImport]

ソースコード

diff # 

#{{{ header
import algorithm, sequtils, tables, macros, math, sets, strutils
when defined(MYDEBUG):
  import header

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld",addr result)
proc nextFloat(): float = scanf("%lf",addr result)
proc nextString(): string =
  var get = false
  result = ""
  while true:
    var c = getchar()
    if int(c) > int(' '):
      get = true
      result.add(c)
    else:
      if get: break
      get = false
template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)
template inf(T): untyped = ((T(1) shl T(sizeof(T)*8-2)) - 1)
#}}}


#{{{ Graph
import sequtils

type
  Edge[T] = object
    src,dst:int
    weight:T
    rev:int
  Edges[T] = seq[Edge[T]]
  Graph[T] = seq[seq[Edge[T]]]

proc initEdge[T](src,dst:int,weight:T,rev:int = -1):Edge[T] =
  var e:Edge[T]
  e.src = src
  e.dst = dst
  e.weight = weight
  e.rev = rev
  return e

proc initGraph[T](n:int):Graph[T] =
  return newSeqWith(n,newSeq[Edge[T]]())

proc addBiEdge[T](g:var Graph[T],src,dst:int,weight:T=1):void =
  g[src].add(initEdge(src,dst,weight,g[dst].len))
  g[dst].add(initEdge(dst,src,weight,g[src].len-1))

proc addEdge[T](g:var Graph[T],src,dst:int,weight:T=1):void =
  g[src].add(initEdge(src,dst,weight,-1))

proc `<`[T](l,r:Edge[T]):bool = l.weight < r.weight
#}}}

var v = newSeq[int]()

# depth first search {{{
proc dfs(g:Graph[int], u:int, p = -1, h = 0) =
  v.add(h)
  for e in g[u]:
    if e.dst == p: continue
    g.dfs(e.dst, u, h + 1)
#}}}

block main:
  let N, K = nextInt()
  if K > N: echo -1;break
  var g = initGraph[int](N)
  for i in 0..<N-1:
    let a, b = nextInt() - 1
    g.addBiEdge(a, b)
  g.dfs(0)
  v.sort()
  echo v[0..<K].sum
  discard
0