AT_future_contest_2020_final_2_a 千の木2

[problemUrl]: https://atcoder.jp/contests/future-contest-2020-final-2/tasks/future_contest_2020_final_2_a 二次元座標平面上に $ 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 $ $ 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 $ 点となる。

### 問題文の変更点 - $ K $ が固定でなくなり、木ごとに $ K_i $ が与えられ、$ 2 $ 以上 $ 100 $ 以下の頂点の木が与えられるようになりました。 - $ c_i $ の生成式を変更しました。中頂点の割合が下がり、弱頂点が増え、$ c_i $ が全体的に少なくなっています。 ### 制約 - $ 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 $ - 入力中の値はすべて整数である。 ### テストケース生成方法 - 各頂点 $ 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 $ 以下の整数から一様ランダムに選ばれる。 ### 入出力例 入力例および出力例は [このリンク](https://img.atcoder.jp/future-contest-2020-final-2/5d0f79985f1f06c9f75730a2d9e72045.zip) からダウンロードできます。