結果

問題 No.763 Noelちゃんと木遊び
ユーザー unaunagiunaunagi
提出日時 2021-08-07 00:21:32
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,349 bytes
コンパイル時間 1,411 ms
コンパイル使用メモリ 89,736 KB
最終ジャッジ日時 2024-04-27 03:54:21
合計ジャッジ時間 2,420 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(20, 6) Error: 'nibutan' can have side effects
> /home/judge/data/code/Main.nim(21, 65) Hint: 'nibutan' calls routine via hidden pointer indirection

ソースコード

diff # 

import sequtils, strutils, strformat, algorithm, math, sugar, hashes, tables
const (INF*, AZ*) = (10^18+9, 26)
import complex, random, deques, heapqueue, sets, macros
var inFile = stdin
let inps* = iterator: string {.closure.} = (while true: (for s in inFile.readLine.split: yield s))
let (inp*, inpf*) = (() => parseInt(inps()), () => parseFloat(inps()))
func chmax*[T](t: var T; v: T): bool{.discardable.} = (let f = (t < v); if f: t = v; f)
func chmin*[T](t: var T; v: T): bool{.discardable.} = (let f = (t > v); if f: t = v; f)
func inRange*[T](L, v, r: T): bool = (L < r) and ((L <= v) and (v < r))
func inRange*(x, y, w, h: int): bool = inRange(0, y, h) and inRange(0, x, w)
func sqrt*(v: int): int = toInt(trunc(sqrt(toFloat(v))))
template if3*(cond: bool; t, f: untyped): auto = (if cond: t else: f)
func divCeil*(a, b: int): int = (a+b-1) div b
template echoQuit*(ans: typed) = (echo(ans); quit(0))
template newSeqWith*(y, x: int; p: untyped): untyped = newSeqWith(y, newSeqWith(x, p))
func hash*(x: int): Hash = x*7
func char2int*(c, def: char): int = ord(c)-ord(def)
func inc*[T](ct: var Table[T, int]; k: T; v = 1) = (ct[k] = ct.getOrDefault(k) + v)
func dec*[T](ct: var Table[T, int]; k: T; v = 1) = (if ct.hasKey(k): (if ct[k] <= v: ct.del(k) else: ct[k] -= v))
func nibutan*(ok, ng: int; isOK: (int)->bool): int = (var (ok, ng) = (ok, ng);
  (while (abs(ok - ng) > 1): (let mid = (ng + ok) div 2; if isOk(mid): ok = mid else: ng = mid)); return ok)
proc echo*(f: float) = echo(fmt"{f:.20f}")
func cmod*[T](n, md: T): T = (n mod md + md) mod md
template addEdges*(g: seq[seq]; n: int; frm, to: untyped) = (for i in 0..n: g[frm].add(to))
when defined(debug): #デバッグ時だけ使える命令など
  template eprintf*(x: typed) = echo("[debug] --- ", x)
else:
  template eprintf*(x: typed) = discard
  macro dump*(x: typed): untyped = discard
{.warning[UnusedImport]: off.} #----- ここまでテンプレ -----

let N = inp()
var G = newSeqWith(N, 0, 0)
for i in 0..<N-1:
  let u, v = inp()-1
  G[u].add(v)
  G[v].add(u)

var dp = newSeqWith(N, (0, 0))
proc dfs(cur, owner: int) =
  var r0 = 0
  var r1 = 1

  for nxt in G[cur]:
    if nxt == owner: continue
    dfs(nxt, cur)
    r0 += max(dp[nxt][0], dp[nxt][1])
    r1 += max(dp[nxt][1]-1, dp[nxt][0])
  dp[cur] = (r0, r1)

dfs(0, -1)

dump(dp)
echo(max(dp[0][0], dp[0][1]))
0