/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
問題文
二次元座標平面上に N 個の頂点、頂点 1, \ldots, N があります。また、S 個の無向木 T_1, \ldots, T_S が与えられます。
あなたの課題は、平面上の頂点を結ぶ辺を何本か張って N 頂点の無向グラフ G を作成し、G から S 個のグラフを「取り出す」ことです。取り出したグラフが T_1, \ldots, T_S に「似ている」ほど高得点となります。以下、各事項について詳細を述べます。
-
平面上の頂点について: 頂点 i (1 \leqq i \leqq N) の座標は (x_i, y_i) であり、これらの座標はすべて 0 以上 1000 以下の整数です。また、各頂点には正の整数値 パワー が定められており、頂点 i のパワーは c_i です。
-
木 T_1, \ldots, T_S について: いずれも、1, \ldots, K の番号が付けられた K 個の頂点を持つ無向木です。便宜上、これらの木は番号 1 の頂点を根とする根付き木として入力され、木 T_i (1 \leqq i \leqq S) における番号 j (2 \leqq j \leqq K) の頂点の親は番号 p_{i,j} の頂点です。
-
辺の追加について: 作成するグラフ G には 0 本以上 100000 本以下の任意の本数の無向辺を張ることができます。ただし、辺 \{i, j\} (i \neq j) を張るには、頂点 i, j 間のユークリッド距離が c_i + c_j 以下でなければなりません。また、自己辺や多重辺を生じさせてはなりません。
-
グラフの取り出しについて: それぞれの木 T_i (1 \leqq i \leqq S) に対して、G の相異なる K 頂点 V_{i,1}, \ldots, V_{i,K} を指定してください。これは、各 j (1 \leqq j \leqq K) について、頂点 V_{i,j} を T_i の番号 j の頂点に対応させることを表します。同じ頂点を複数の木に対して用いても構いません。
-
得点について: それぞれの木 T_i (1 \leqq i \leqq S) について以下のように点数を算出し、S 個の木に対する点数の合計がそのテストケースにおけるあなたの得点となります。
-
ある整数 x, y (1 \leqq x, y \leqq K) が存在して、T_i が辺 \{x, y\} を持つが G が辺 \{V_{i,x}, V_{i,y}\} を持たないとき: 0 点
-
そうでないとき、整数の組 (x, y) (1 \leqq x, y \leqq K) であって、G が辺 \{V_{i,x}, V_{i,y}\} を持つが T_i が辺 \{x, y\} を持たないものの個数を e_i とする。
- e_i = 0 のとき: 100 点
- e_i = 1 のとき: 10 点
- e_i = 2 のとき: 1 点
- e_i \geqq 3 のとき: 0 点
-
制約
- N = 1000
- S = 1000
- K = 20
- 0 \leqq x_i, y_i \leqq 1000
- 1 \leqq c_i \leqq 1500
- 1 \leqq p_{i,j} \leqq j-1
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N S K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
p_{1,2} p_{1,3} \ldots p_{1,K}
p_{2,2} p_{2,3} \ldots p_{2,K}
:
p_{S,2} p_{S,3} \ldots p_{S,K}
出力
以下の形式で出力せよ。
M
A_1 B_1
A_2 B_2
:
A_M B_M
V_{1,1} V_{1,2} \ldots V_{1,K}
V_{2,1} V_{2,2} \ldots V_{2,K}
:
V_{S,1} V_{S,2} \ldots V_{S,K}
これは、作られたグラフ G が M (0 \leqq M \leqq 100000) 本の辺 \{A_1, B_1\}, \{A_2, B_2\}, \ldots, \{A_M, B_M\} (1 \leqq A_i, B_i \leqq N) を持つことを表す。辺は任意の順で出力してよく、各辺の端点を出力する順も任意でよい。V_{i,j} (1 \leqq V_{i,j} \leqq N) に関しては問題文本文を参照せよ。
テストケースは 50 個与えられる。各テストケースについて、問題文本文に記載された通りに点数が計算され、全てのテストケースに対する点数の合計がその提出の得点となる。
上記のフォーマットに違反する出力や、またはその他の何らかの欠陥 (例: 自己辺や多重辺の存在、一度の取り出しにおける頂点の重複) のある出力は「不正解」と判定されることがある。この場合、そのテストケースが入力例として与えられているものであれば、そのテストケースでの得点が 0 点となる。その他のテストケースであれば、入力例以外の全てのテストケースでの得点が 0 点となる。
テストケース生成方法
-
各頂点 i (1 \leqq i \leqq N) の座標 x_i, y_i は、それぞれ 0 以上 1000 以下の整数から一様ランダムに選ばれる。これら 2N 個の座標はすべて独立に選ばれ、複数の点が一致しても再抽選などは行われない。
-
各頂点 i (1 \leqq i \leqq N) は、5% の確率で 強頂点、30% の確率で 中頂点、65% の確率で 弱頂点 となる。これに基づき、c_i が以下の範囲の整数から一様ランダムに選ばれる。
- 強頂点: 500 以上 1500 以下
- 中頂点: 200 以上 500 以下
- 弱頂点: 1 以上 200 以下
-
各 i, j (1 \leqq i \leqq S, 2 \leqq j \leqq K) に対し、木 T_i の番号 j の頂点の親 p_{i,j} は 1 以上 j - 1 以下の整数から一様ランダムに選ばれる。
入出力例
入力例および出力例は このリンク からダウンロードできます。