Skip to content

ALGO ARTISプログラミングコンテスト2025冬(AHC041)

問題概要

  • N(=1000)頂点M辺の連結な無向平面グラフGが与えられ、各頂点には美しさA_iが設定されている
  • ここで、以下のような根付き木の集合を考える
    • 各根付き木に含まれる辺はGに含まれる
    • Gの各頂点はちょうど1つの根付き木に属する
    • 各根付き木の頂点の高さは、根からの距離で、すべてH(=10)以下になっている
  • 根付き木Tの見栄えa(T)をΣ(h_v+1)*A_vと定義し、1+Σa(T)が得点となる
  • できるだけ得点が高くなるように根付き木の集合を構築せよ
    • 出力は、各頂点の親の頂点番号を出力する

時間

  • 4 時間

個人的メモ

解説

(50位まで&発言を見つけられた方のみ)