004 - 魔女っ娘ヒナくるん -Magic.Finale

Magic.Finale 『Share Hinacle with you』

前回までのあらすじ

なんとコティーヤを撃破しただけではなく、改心させてしまったヒナくるん！！
平和になった世界に喜ぶパルスィ姫達。 そこにヒナくるんが、ある提案を持ちかける・・・

本編

コティーヤ
「流石は 《魔女っ娘ヒナくるん》 と呼ばれているだけあるわね・・・
この私を、改心させてしまうなんて・・・」

パルスィ姫
「これが彼女よ。私が惚れた理由も分かるでしょう？」

ヒナくるん
「えっへん！！
それよりね！こうして世界が平和になったじゃない！！
この幸せを、幻想郷中のみんなに伝えられないかな！！」

パルスィ姫
「それはいい考えね。でも、どうやって伝えるの？
天狗の力を借りるのかしら？」

ヒナくるん
「そんなの遅すぎて退屈しちゃうわ！！
今すぐよ！！今すぐ届けるの！！」

パルスィ姫
「貴女それアヤが聞いたら怒るわよ・・・
それに天狗より早い方法なんて・・・」

ニトゥーリ
「可能だよ。パルスィ姫、コティーヤ様。
私の手元に、幻想郷全住人の居場所を記したデータがある。
姫のテレパルスィーとコティーヤ様の奇跡があれば、
一秒もかからずにヒナくるんの持つ幸福を全員に伝えることができるわ。」

コティーヤ
「ニトゥーリ、貴方・・・
そうね、やってみましょう。」

問題

ついにこの物語も、終わりを迎えようとしている。
あなた自身の手で、物語に幕を閉じるのだ。

ヒナくるんは、幻想郷に住む人々全員に幸福を伝えようとしている。
彼女たちは、幻想郷に住む住人の数、居場所、交友関係を示した情報を持っている。

ここでニトゥーリが、ある追加データを用意した。
パルスィ姫が繋げることができる住人のペア、
そのペアを繋げるにあたってパルスィ姫が必要とする魔力の大きさを記したリストと、
コティーヤが奇跡の力で幸せを伝えることの出来る領域の範囲を記したリストだ。

コティーヤは、奇跡の力によって、
ある領域内の住人全員に幸せを届けることができる。
カバーできる領域は重複することがある。
コティーヤは魔力が無尽蔵にあるため、魔力切れの心配はない。

パルスィ姫は、テレパルスィーを用いることで、リストに記されたある住人と住人の間に、
魔力を消費することで幸せを届けるリンクラインを生み出すことが出来る。
交友関係のある住人同士にもリンクラインを生み出すことが可能で、
この際は幸せを届けるリンクラインを作る際の魔力がかからない。
ただし、パルスィ姫とコティーヤの力が干渉するのを防ぐ為、
コティーヤの力が及ぶ範囲内にある点に対してリンクを繋ぐ行為はしてはいけない。
追記：リンクライン自体はコティーヤの奇跡による影響を受けない。
メタく言えば考慮するのは点がコティーヤの範囲内にあるか無いかだけで良いということだ。

ヒナくるんは、コティーヤとの決戦で疲弊しており、一人にしか幸福を伝えることが出来ない。
なのでパルスィ姫は、テレパルスィーを使ってかつできるだけ少ない魔力を使って全員に幸福が行き渡るようにしたい。

つまりは、コティーヤの奇跡でカバーできない範囲については、
全ての点が繋がれてなければならないのだ。

あなたには、全ての住人に幸せを伝えることが可能になるようにリンクを張った時の、
パルスィ姫の消費する魔力の最小値を求めてもらいたい。
もしもどうしても全員に幸せを伝えることが出来ない場合は、
それは放送事故に他ならない。

さあ、君の手で、この旅を終わらせよう。

入出力形式

一行目に、ヒナくるんが幸福を伝えたい箇所の数 A ,
　　　　　パルスィ姫がリンク可能な伝達経路の数 B ,
　　　　　コティーヤの奇跡により魔力無しでカバーできる範囲の数 C ,
　　　　　友好関係のあるペアの数を示す D が空白区切りで与えられる。

続いてA行に渡り、ヒナくるんが幸福を伝えたい箇所（点）の座標 Hx_i , Hy_i が空白区切りで与えられる。
座標は、左下を(0,0)とし、右上を(INF,INF)とする。

続いてB行に渡り、パルスィ姫が伝達可能な経路のペア P1_i , P2_i ,
　そこを繋げる為に必要になる魔力 P3_i が空白区切りで与えられる。

続いてC行に渡り、コティーヤがカバーできる範囲のX軸の範囲 sx_i , gx_i ,
　Y軸の範囲 sy_i , gy_i が空白区切りで与えられる。
　ある箇所の座標が sx ≦ Hx ≦ gx かつ sy ≦ Hy ≦ gy を満たしている時、
　そこに幸福を伝えることができる。
　パルスィ姫とコティーヤの力が干渉するのを防ぐ為、
　コティーヤの力が及ぶ範囲内にある点に対してリンクを繋ぐ行為はしてはいけない。

続いてD行に渡り、友好関係のあるペア L1_i , L2_i が空白区切りで与えられる。
L1とL2の間では、魔力を使用せずにリンクラインを張ることが可能な点に注意せよ。

ヒナくるんが全員に幸福を伝える為に必要な魔力の最小値を一行に出力せよ。
全員に幸福を伝えることが出来ない場合、 "Broadcasting accident" を一行に出力せよ。

制約

• 全ての値は非負整数である。
• コティーヤの力が及ぶある一つの範囲に含まれる点の数は100以下である。
• 0 ≦ A ≦ 10,000
• 0 ≦ B ≦ 100,000
• 0 ≦ C ≦ 10,000
• 0 ≦ D ≦ 1,000
• 0 ≦ Hx,Hy,sx,sy,gx,gy ≦ 1,000,000,000
• (0 ≦ P1≠P2,L1,L2 ＜ A) , (0 ≦ P3 ≦ 10,000)
• (sx ≦ gx) , (sy ≦ gy)
• 0 ≦ i ＜ (A,B,C,D)

部分点

配点の20%分は、 C ≦ 10 を満たす。

入出力例

入力例一

5 6 1 1
0 0
4 0
0 4
4 4
2 2
0 1 3
0 2 2
1 3 5
2 3 2
0 4 2
3 4 5
1 3 1 3
1 3

出力例一

4

点0と点2、点2と点3を繋ぐことにより、全ての場所に幸福を伝えることが可能となる。

---

入力例二

5 6 1 2
0 0
4 0
0 4
4 4
2 2
0 1 3
0 2 2
1 3 5
2 3 2
0 4 2
3 4 5
1 3 1 3
3 4
0 4

出力例二

7

点0と点4、点4と点3は魔力を使わずに繋げることが可能であるが、、
コティーヤの力が及ぶ範囲内にあるため繋げることが出来ない。
点0と点1、点2と点3、点0と点2を繋げる事で全ての場所に幸福を伝えることが可能となる。

---

入力例三

5 4 1 0
0 0
4 0
0 4
4 4
2 2
0 2 3
1 3 2
0 4 2
3 4 5
1 3 1 3

出力例三

Broadcasting accident

点4がコティーヤの力が及ぶ範囲内にあるため、
点0から点4や、点4から点3にリンクを張ることはできない。