結果
問題 | No.1103 Directed Length Sum |
ユーザー | chaemon |
提出日時 | 2020-07-03 21:41:26 |
言語 | Nim (2.0.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,533 bytes |
コンパイル時間 | 3,474 ms |
コンパイル使用メモリ | 75,500 KB |
実行使用メモリ | 318,848 KB |
最終ジャッジ日時 | 2024-09-16 23:46:27 |
合計ジャッジ時間 | 10,594 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | WA | - |
testcase_03 | AC | 281 ms
171,960 KB |
testcase_04 | AC | 377 ms
64,212 KB |
testcase_05 | AC | 753 ms
108,132 KB |
testcase_06 | AC | 224 ms
43,784 KB |
testcase_07 | AC | 39 ms
12,544 KB |
testcase_08 | AC | 62 ms
17,408 KB |
testcase_09 | AC | 25 ms
8,960 KB |
testcase_10 | AC | 92 ms
23,428 KB |
testcase_11 | AC | 405 ms
69,376 KB |
testcase_12 | AC | 208 ms
43,168 KB |
testcase_13 | AC | 90 ms
23,696 KB |
testcase_14 | AC | 19 ms
7,424 KB |
testcase_15 | AC | 155 ms
34,232 KB |
testcase_16 | AC | 473 ms
79,056 KB |
testcase_17 | AC | 523 ms
81,864 KB |
testcase_18 | AC | 88 ms
23,496 KB |
testcase_19 | AC | 425 ms
70,900 KB |
testcase_20 | AC | 30 ms
10,496 KB |
testcase_21 | AC | 57 ms
16,300 KB |
testcase_22 | AC | 315 ms
59,480 KB |
testcase_23 | AC | 171 ms
36,276 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 # 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 #}}} let p = g.dfs(root) echo ans