結果

問題 No.1103 Directed Length Sum
ユーザー chaemonchaemon
提出日時 2020-07-03 21:43:05
言語 Nim
(2.0.2)
結果
AC  
実行時間 783 ms / 3,000 ms
コード長 4,577 bytes
コンパイル時間 5,267 ms
コンパイル使用メモリ 76,500 KB
実行使用メモリ 319,712 KB
最終ジャッジ日時 2023-10-17 00:06:33
合計ジャッジ時間 12,859 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 474 ms
319,712 KB
testcase_03 AC 313 ms
174,784 KB
testcase_04 AC 399 ms
64,792 KB
testcase_05 AC 783 ms
110,044 KB
testcase_06 AC 239 ms
43,092 KB
testcase_07 AC 43 ms
12,852 KB
testcase_08 AC 68 ms
17,876 KB
testcase_09 AC 27 ms
9,328 KB
testcase_10 AC 110 ms
24,064 KB
testcase_11 AC 435 ms
69,764 KB
testcase_12 AC 228 ms
44,268 KB
testcase_13 AC 107 ms
25,336 KB
testcase_14 AC 21 ms
7,840 KB
testcase_15 AC 177 ms
34,444 KB
testcase_16 AC 503 ms
79,112 KB
testcase_17 AC 534 ms
82,760 KB
testcase_18 AC 97 ms
24,024 KB
testcase_19 AC 439 ms
71,268 KB
testcase_20 AC 32 ms
10,596 KB
testcase_21 AC 61 ms
16,512 KB
testcase_22 AC 368 ms
59,292 KB
testcase_23 AC 196 ms
36,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#{{{ header
{.hints:off warnings:off optimization:speed.}
import algorithm, sequtils, tables, macros, math, sets, strutils, strformat, sugar
when defined(MYDEBUG):
  import header

import streams
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[F](f:F): string =
  var get = false
  result = ""
  while true:
#    let c = getchar()
    let c = f.readChar
    if c.int > ' '.int:
      get = true
      result.add(c)
    elif get: return
proc nextInt[F](f:F): int = parseInt(f.nextString)
proc nextFloat[F](f:F): float = parseFloat(f.nextString)
proc nextString():string = stdin.nextString()

template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)
template inf(T): untyped = 
  when T is SomeFloat: T(Inf)
  elif T is SomeInteger: ((T(1) shl T(sizeof(T)*8-2)) - (T(1) shl T(sizeof(T)*4-1)))
  else: assert(false)

proc discardableId[T](x: T): T {.discardable.} =
  return x
macro `:=`(x, y: untyped): untyped =
  var strBody = ""
  if x.kind == nnkPar:
    for i,xi in x:
      strBody &= fmt"""
{xi.repr} := {y[i].repr}
"""
  else:
    strBody &= fmt"""
when declaredInScope({x.repr}):
  {x.repr} = {y.repr}
else:
  var {x.repr} = {y.repr}
"""
  strBody &= fmt"discardableId({x.repr})"
  parseStmt(strBody)


proc toStr[T](v:T):string =
  proc `$`[T](v:seq[T]):string =
    v.mapIt($it).join(" ")
  return $v

proc print0(x: varargs[string, toStr]; sep:string):string{.discardable.} =
  result = ""
  for i,v in x:
    if i != 0: addSep(result, sep = sep)
    add(result, v)
  result.add("\n")
  stdout.write result

var print:proc(x: varargs[string, toStr])
print = proc(x: varargs[string, toStr]) =
  discard print0(@x, sep = " ")

template makeSeq(x:int; init):auto =
  when init is typedesc: newSeq[init](x)
  else: newSeqWith(x, init)

macro Seq(lens: varargs[int]; init):untyped =
  var a = fmt"{init.repr}"
  for i in countdown(lens.len - 1, 0): a = fmt"makeSeq({lens[i].repr}, {a})"
  parseStmt(a)

template makeArray(x; init):auto =
  when init is typedesc:
    var v:array[x, init]
  else:
    var v:array[x, init.type]
    for a in v.mitems: a = init
  v

macro Array(lens: varargs[typed], init):untyped =
  var a = fmt"{init.repr}"
  for i in countdown(lens.len - 1, 0):
    a = fmt"makeArray({lens[i].repr}, {a})"
  parseStmt(a)
# }}}

# 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]]]
  Matrix[T] = seq[seq[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],e:Edge[T]):void =
  var e_rev = e
  swap(e_rev.src, e_rev.dst)
  let (r, s) = (g[e.src].len, g[e.dst].len)
  g[e.src].add(e)
  g[e.dst].add(e_rev)
  g[e.src][^1].rev = s
  g[e.dst][^1].rev = r
proc addBiEdge[T](g:var Graph[T],src,dst:int,weight:T=1):void =
  g.addBiEdge(initEdge(src, dst, weight))

proc initUndirectedGraph[T](n:int, a,b,c:seq[T]):Graph[T] =
  result = initGraph[T](n)
  for i in 0..<a.len: result.addBiEdge(a[i], b[i], c[i])
proc initUndirectedGraph[T](n:int, a,b:seq[T]):Graph[T] =
  result = initGraph[T](n)
  for i in 0..<a.len: result.addBiEdge(a[i], b[i], T(1))
proc initGraph[T](n:int, a,b:seq[int],c:seq[T]):Graph[T] =
  result = initGraph[T](n)
  for i in 0..<a.len: result.addEdge(a[i], b[i], c[i])
proc initGraph[T](n:int, a,b:seq[int]):Graph[T] =
  result = initGraph[T](n)
  for i in 0..<a.len: result.addEdge(a[i], b[i], T(1))


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

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

N := nextInt()
g := initGraph[int](N)
ind := Seq(N, 0)
outd := Seq(N, 0)
for i in 0..<N-1:
  let a, b = nextInt() - 1
  g.addEdge(a, b)
  outd[a].inc
  ind[b].inc

root := 0
for u in 0..<N:
  if ind[u] == 0: root = u; break
ans := 0

const Mod = 1000000007

# depth first search {{{
proc dfs[T](g:Graph[T], u:int, p = -1):tuple[n, s:int] = # num, sum
  result = (1, 0)
  for e in g[u]:
    if e.dst == p: continue
    var t = g.dfs(e.dst, u)
    t.s += t.n
    result.n += t.n
    result.s += t.s
  ans += result.s
  ans = ans mod Mod
#}}}

let p = g.dfs(root)
echo ans
0