問題文の変更点

• $K$ が固定でなくなり、木ごとに $K_i$ が与えられ、$2$ 以上 $100$ 以下の頂点の木が与えられるようになりました。
• $c_i$ の生成式を変更しました。中頂点の割合が下がり、弱頂点が増え、$c_i$ が全体的に少なくなっています。

問題文

二次元座標平面上に $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_i$ 個の頂点を持つ無向木です。便宜上、これらの木は番号 $1$ の頂点を根とする根付き木として入力され、木 $T_i$ $(1 \\leqq i \\leqq S)$ における番号 $j$ $(2 \\leqq j \\leqq K_i)$ の頂点の親は番号 $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_i$ 頂点 $V_{i,1}, \\ldots, V_{i,K_i}$ を指定してください。これは、各 $j$ $(1 \\leqq j \\leqq K_i)$ について、頂点 $V_{i,j}$ を $T_i$ の番号 $j$ の頂点に対応させることを表します。同じ頂点を複数の木に対して用いても構いません。

• 得点について: それぞれの木 $T_i$ $(1 \\leqq i \\leqq S)$ について以下のように点数を算出し、$S$ 個の木に対する点数の合計がそのテストケースにおけるあなたの得点となります。

• ある整数 $x, y$ $(1 \\leqq x, y \\leqq K_i)$ が存在して、$T_i$ が辺 $\\{x, y\\}$ を持つが $G$ が辺 $\\{V_{i,x}, V_{i,y}\\}$ を持たないとき: $0$ 点

• そうでないとき、整数の組 $(x, y)$ $(1 \\leqq x, y \\leqq K_i)$ であって、$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$
• $2 \\leqq K_i \\leqq 100$
• $0 \\leqq x_i, y_i \\leqq 1000$
• $1 \\leqq c_i \\leqq 1500$
• $1 \\leqq p_{i,j} \\leqq j-1$
• 入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $S$ $x_1$ $y_1$ $c_1$ $x_2$ $y_2$ $c_2$ $:$ $x_N$ $y_N$ $c_N$ $K_1$ $p_{1,2}$ $p_{1,3}$ $\\ldots$ $p_{1,K_1}$ $K_2$ $p_{2,2}$ $p_{2,3}$ $\\ldots$ $p_{2,K_2}$ $:$ $K_S$ $p_{S,2}$ $p_{S,3}$ $\\ldots$ $p_{S,K_S}$

出力

以下の形式で出力せよ。

$M$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$ $V_{1,1}$ $V_{1,2}$ $\\ldots$ $V_{1,K_1}$ $V_{2,1}$ $V_{2,2}$ $\\ldots$ $V_{2,K_2}$ $:$ $V_{S,1}$ $V_{S,2}$ $\\ldots$ $V_{S,K_S}$

これは、作られたグラフ $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$% の確率で 強頂点、$10$% の確率で 中頂点、$85$% の確率で 弱頂点 となる。これに基づき、$c_i$ が以下の範囲の整数から一様ランダムに選ばれる。

• 強頂点: $200$ 以上 $500$ 以下

• 中頂点: $50$ 以上 $200$ 以下

• 弱頂点: $1$ 以上 $50$ 以下

• 各 $i, j$ $(1 \\leqq i \\leqq S, 2 \\leqq j \\leqq K_i)$ に対し、木 $T_i$ の番号 $j$ の頂点の親 $p_{i,j}$ は $1$ 以上 $j - 1$ 以下の整数から一様ランダムに選ばれる。

入出力例

入力例および出力例は このリンク からダウンロードできます。