結果

問題 No.1484 木に数を書き込む問題 / Just Write Numbers! 2
ユーザー dot_haraai
提出日時 2021-05-09 15:02:08
言語 Nim
(2.2.0)
結果
WA  
実行時間 -
コード長 1,923 bytes
コンパイル時間 4,180 ms
コンパイル使用メモリ 88,524 KB
実行使用メモリ 62,992 KB
最終ジャッジ日時 2024-09-18 21:09:58
合計ジャッジ時間 11,809 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 2 WA * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 18) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'times' [UnusedImport]
/home/judge/data/code/Main.nim(2, 37) Warning: imported and not used: 'deques' [UnusedImport]
/home/judge/data/code/Main.nim(2, 26) Warning: imported and not used: 'strformat' [UnusedImport]
/home/judge/data/code/Main.nim(2, 18) Warning: imported and not used: 'future' [UnusedImport]
/home/judge/data/code/Main.nim(2, 8) Warning: imported and not used: 'critbits' [UnusedImport]
/home/judge/data/code/Main.nim(1, 52) Warning: imported and not used: 'tables' [UnusedImport]
/home/judge/data/code/Main.nim(1, 60) Warning: imported and not used: 'sets' [UnusedImport]
/home/judge/data/code/Main.nim(1, 66) Warning: imported and not used: 'lists' [UnusedImport]
/home/judge/data/code/Main.nim(1, 73) Warning: imported and not used: 'intsets' [UnusedImport]

ソースコード

diff # 

import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets
import critbits, future, strformat, deques,heapqueue
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
template `mod=`(x,y) = x = x mod y
template scan2 = (scan(), scan())
template scan3 = (scan(), scan())
let read* = iterator: string {.closure.} =
    while true: (for s in stdin.readLine.split: yield s)
proc scan(): int = read().parseInt
proc scanf(): float = read().parseFloat
proc toInt(c:char): int =
  return int(c) - int('0')




proc solve()=
  var 
    n = scan()
    es = newseqwith(n,newseq[int]())
    ccnt = newseqwith(n,newseq[int]())
    depth = newseqwith(n,0)
    fp = newseqwith(n,false)
    ans = newseqwith(n,0)
  for i in 0..<n-1:
    var
      a = scan()-1
      b = scan()-1
    es[a].add(b)
    ccnt[a].add(0)
    es[b].add(a)
    ccnt[b].add(0)

  # 各頂点の子要素の個数と深さ
  proc dfs(s:int):(int,int)=# 個数、深さ
    result=(1,1)
    fp[s]=true
    for idx,nxt in es[s]:
      if fp[nxt]:continue
      var (c,d) = dfs(nxt)
      depth[s].max=d+1
      ccnt[s][idx]=c
      result[0]+=c
    result[1]=depth[s]
    return result

  var score = 0
  proc dfs2(s:int,num:int)=
    #echo fmt"{s} , {num}, {score}"
    ans[s] = num
    # s:現在の頂点番号
    # num:現在の頂点の値
    var
      # q:(子要素の深さ,子頂点)
      q = initHeapQueue[(int,int)]()
    var tnum = num
    fp[s] = true
    for idx, nxt in es[s]:
      if fp[nxt]:continue
      q.push((depth[nxt]+1,idx))
    var
      lastdepth:int = 0
      cnt:int
      nxt:int
    while q.len>0:
      var (dpt,idx) = q.pop()
      cnt = ccnt[s][idx]
      nxt = es[s][idx]
      score+=1+lastdepth
      dfs2(nxt,tnum+1)
      
      lastdepth = dpt
      tnum+=cnt
    
      


  


  discard dfs(0)
  #echo ccnt
  #echo depth
  fp.fill(false)
  dfs2(0,0)
  echo score
  #echo ans


solve()
0