/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
ストーリー
AtCoderオフィスでは、一足遅いクリスマスパーティーの準備が進められている。高橋社長は、クリスマスツリーに使う根付き木を切りに行くことにした。
根付き木の各頂点は 美しさ を持ち、高いところに美しい頂点が存在するとパーティー会場の 見栄え が良くなる。ただし、根付き木が高すぎるとAtCoderオフィスの天井にぶつかってしまうため、パーティー会場に持ち込むことのできる根付き木の高さには制限がかけられている。
与えられたグラフから根付き木をいくつか切り出して、できるだけパーティー会場の 見栄え を良くして欲しい。
問題文
N 頂点 M 辺の連結な無向平面グラフ G が与えられる。頂点には 0 から N-1 の番号が、辺には 0 から M-1 の番号がそれぞれ付けられている。頂点 v の座標は (x_v, y_v) であり、 辺 i は頂点 u_i と v_i を結んでいる。各頂点には正の整数をとる 美しさ が定められており、頂点 v の 美しさ は A_v である。
根付き木 T の 見栄え を以下のように定義する。 T における頂点 v の 高さ h_v を、根から v へのパスに含まれる辺の本数とする。 このとき、根付き木 T の 見栄え a(T) は a(T):=\sum_{v\in T} (h_v + 1) A_v と定義される。
与えられたグラフ G から以下の条件を満たすような根付き木の集合を構築し、見栄え の総和をできるだけ大きくせよ。
- 各根付き木 T に含まれる辺は全て G に含まれる。
- G の各頂点はちょうど 1 つの根付き木に属する。
- 各根付き木における頂点の高さは全て H 以下である。
得点
出力した根付き木の集合を F としたとき、1+\sum_{T\in F}a(T) の得点が得られる。
合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
N M H
A_0 \cdots A_{N-1}
u_0 v_0
\vdots
u_{M-1} v_{M-1}
x_0 y_0
\vdots
x_{N-1} y_{N-1}
入力は以下の制約を満たす。
- N=1000
- 1000\le M \le 3000
- H=10
- 1\le A_v\le 100
- 0\le u_i \lt v_i\le N-1
- 0\le x_v, y_v\le 1000
- (x_v, y_v) は全て異なる。
- 入力は全て整数。
- 与えられるグラフは連結な平面グラフであり、頂点 v を座標 (x_v, y_v) に配置し、各辺を両端点を結ぶ線分として描画した時、どの二辺も端点以外に共通点を持たないことが保証されている。
出力
構築した根付き木の集合における頂点 v の親の頂点番号を p_v（v が根の場合は p_v=-1）として、以下の形式で標準出力に出力せよ。
p_0 p_1 \cdots p_{N-1}
解は複数回出力しても良い。 複数出力された場合、一番最後に出力された解のみが採点に用いられる。 Web版のビジュアライザを用いると、複数の解の比較が可能である。
入力生成方法
L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L,U) と表す。
グラフ G の生成
中心 (500,500) 、半径 500 の円に含まれる格子点からランダムに点を一つずつ、合計 N 個選んで (x_0, y_0), \cdots, (x_{N-1}, y_{N-1}) とする。ただし、既に選んだ点とのユークリッド距離が 15 以下の場合は選び直す。
以上により得られた頂点集合 V に対してドロネー三角形分割を計算し、三角形分割の辺集合を E として G=(V, E) とする。
美しさ A の生成
頂点 v の美しさは A_v=\mathrm{rand}(1, 100) により生成する。
ツール(入力ジェネレータ・ローカルテスタ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。
Story
At the AtCoder office, preparations are underway for a slightly belated Christmas party. CEO Takahashi has decided to go cut down rooted trees to use as the Christmas trees.
Each vertex in a rooted tree has a beauty value, and the party venue looks more attractive if beautiful vertices are located high. However, if the rooted tree is too tall, it will hit the ceiling of the AtCoder office. Therefore, there is a limit to the height of rooted trees that can be brought into the venue.
Your task is to cut out several rooted trees from a given graph to maximize the attractiveness of the party venue.
Problem Statement
You are given a connected, undirected planar graph G with N vertices and M edges. The vertices are numbered from 0 to N-1, and the edges are numbered from 0 to M-1. The coordinates of vertex v are (x_v, y_v), and edge i connects vertices u_i and v_i. Each vertex has a beauty value, which is a positive integer. The beauty value of vertex v is A_v.
The attractiveness of a rooted tree T is defined as follows: Let the height h_v of vertex v in T be the number of edges in the path from the root to v. The attractiveness a(T) of the rooted tree T is defined as a(T):=\sum_{v \in T} (h_v + 1) A_v.
Your task is to construct a set of rooted trees from the given graph G that satisfies the following conditions, and make the sum of attractiveness as large as possible:
- All edges in each rooted tree T must belong to G.
- Each vertex in G belongs to exactly one rooted tree.
- The height of all vertices in each rooted tree must be less than or equal to H.
Scoring
Let F be the set of rooted trees you construct. Then, you will obtain a score of 1+\sum_{T\in F}a(T).
There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.
Input
Input is given from Standard Input in the following format:
N M H
A_0 \cdots A_{N-1}
u_0 v_0
\vdots
u_{M-1} v_{M-1}
x_0 y_0
\vdots
x_{N-1} y_{N-1}
The input satisfies the following constraints:
- N = 1000
- 1000 \leq M \leq 3000
- H = 10
- 1 \leq A_v \leq 100
- 0 \leq u_i < v_i \leq N-1
- 0 \leq x_v, y_v \leq 1000
- (x_v, y_v) are all distinct.
- All inputs are integers.
- The given graph is a connected planar graph. If vertex v is placed at coordinate (x_v, y_v), and each edge is drawn as a line segment connecting its endpoints, no two edges share points other than their endpoints.
Output
Let p_v be the parent of vertex v in the constructed set of rooted trees. If v is a root, let p_v=-1. Then, output to Standard Output in the following format:
p_0 p_1 \cdots p_{N-1}
Your program may output multiple solutions. If multiple solutions are output, only the last one is used for scoring. You can compare multiple solutions using the web version of the visualizer.
Input Generation
Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.
Generation of the graph G
Randomly select N points (x_0,y_0),\cdots,(x_{N-1},y_{N-1}) from the lattice points contained in a circle with center (500,500) and radius 500. If the Euclidean distance between (x_i,y_i) and an already selected point (x_j,y_j) (j<i) is less than or equal to 15, we select (x_i,y_i) again.
For the vertex set V obtained as described above, compute the Delaunay triangulation, define the edge set of the triangulation as E, and let G = (V, E).
Generation of the beauty values A
For each vertex v, the beauty value A_v is generated using \mathrm{rand}(1, 100).
Tools (Input generator, local tester and visualizer)
- Web version: This is more powerful than the local version and can display animations.
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.