結果
問題 | No.1103 Directed Length Sum |
ユーザー | chaemon |
提出日時 | 2020-07-03 21:43:05 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 846 ms / 3,000 ms |
コード長 | 4,577 bytes |
コンパイル時間 | 5,256 ms |
コンパイル使用メモリ | 75,940 KB |
実行使用メモリ | 318,080 KB |
最終ジャッジ日時 | 2024-09-16 23:48:49 |
合計ジャッジ時間 | 14,013 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 611 ms
318,080 KB |
testcase_03 | AC | 322 ms
171,648 KB |
testcase_04 | AC | 462 ms
63,744 KB |
testcase_05 | AC | 846 ms
108,160 KB |
testcase_06 | AC | 283 ms
42,496 KB |
testcase_07 | AC | 49 ms
12,416 KB |
testcase_08 | AC | 85 ms
17,512 KB |
testcase_09 | AC | 30 ms
8,832 KB |
testcase_10 | AC | 134 ms
22,784 KB |
testcase_11 | AC | 507 ms
69,248 KB |
testcase_12 | AC | 296 ms
43,264 KB |
testcase_13 | AC | 136 ms
23,552 KB |
testcase_14 | AC | 22 ms
7,552 KB |
testcase_15 | AC | 230 ms
34,308 KB |
testcase_16 | AC | 599 ms
77,696 KB |
testcase_17 | AC | 614 ms
81,024 KB |
testcase_18 | AC | 126 ms
22,784 KB |
testcase_19 | AC | 518 ms
70,784 KB |
testcase_20 | AC | 37 ms
10,240 KB |
testcase_21 | AC | 75 ms
16,292 KB |
testcase_22 | AC | 429 ms
58,496 KB |
testcase_23 | AC | 234 ms
36,224 KB |
ソースコード
#{{{ 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