0058 - かえるぴょんぴょん

問題文

浜松工業高校内にあるプールには、N 枚の葉っぱが浮かんでいる。それぞれの葉っぱには、1 から N の番号がふられていて、それぞれ 1 匹ずつかえるが住んでいる。

このかえるたちは普段から、自分のすみかにとどまって一日中ぼーとしていた。しかし最近、ボーっといていたツケがまわってきて ちょっと太ってきた。このままだと牛になってしまう。そこでかえるたちは散歩することを考え、我々に相談してきた。

かえるたちは、我々が教えた 2 つの葉っぱ間の経路のみを使って移動することができる。最初、かえるたちは 1 つも経路を知らない。経路はたくさん教えることができ、それぞれの経路は教えてすぐにすべてのかえると共有される。我々は 2 匹のかえるを選んで、それぞれのかえるを散歩させる命令を出すことができる。2 匹のかえるは命令をうけた直後に必ずスタートし、もう 1 方の葉っぱ(相手がもともと住んでいた葉っぱ)を目的の葉っぱとして、そこに目指して移動する。かえるたちは頭があまりよくないので、目的の葉っぱに到達するまでに 同じ道を何度も通ったりすることがある。しかし、かえるたちは意思疎通のプロなので、同時に目的の葉っぱに到着するように道を進む。ただし、経路の途中でその経路を引き返すことはない。

しかしこの散歩には、かえる同士が衝突する可能性があった。それぞれのかえるは必ず時間 1 ごとに単位距離 1 のジャンプをして移動する。かえるがジャンプしている間は俊敏な体を活かして衝突を回避するのだが、着地地点が同じ場合 回避できない。それぞれのかえるが最短経路を進んでくれれば衝突するかしないか分かるのだが、今回いろいろな経路があり得るため衝突するかの判断が難しい。そこで、衝突する可能性があるかどうか調べることにした。

なおかえるの散歩中、他のかえるは隠れているのでそのかえると衝突することはない。

7/22 11:35追記 散歩の命令について、一方のかえるが目的の葉っぱに到着しても、別の葉っぱへ移動することはできるものとする。

入力

N Q
w1 x1 y1 z1
w2 x2 y2 z2
:
wQ xQ yQ zQ

• 1 行目には かえるの引数 N(1 ≦ N ≦ 10⁵) と与えられる情報の個数 Q(1 ≦ Q ≦ 10⁵) が半角空白区切りで与えられる。
• 2 行目からの Q 行のうち i 行目には i 番目の情報を表す整数 w_i, x_i, y_i, z_i が半角空白区切りに与えられる。各変数は以下の制約を満たす。
• 1 ≦ w_i ≦ 2
• 1 ≦ x_i, y_i ≦ N
• x_i ≠ y_i
• 1 ≦ z_i ≦ 10⁹
• W_i = 1 のとき、 葉っぱ x_i と 葉っぱ y_i の間に長さ z_i メートルの経路を教えることを表す。
• w_i = 2 のとき、 葉っぱ x_i にいるかえる と 葉っぱ y_i にいるかえるを散歩させる命令を行ったことを表す。このとき z_i は不定である。
• 同じ 2 つの葉っぱに複数本の経路が教えられることもある。
• 我々が命令した時点では、それ以前のかえるの散歩は終了していることとする。

出力

入力は複数行からなる。我々が命令するたびに、2 匹のかえるが衝突する可能性があるならば、"HIT" を、 必ず衝突しない場合は、"GOOD" を 1 行に出力せよ。また、そもそも一方の葉にたどりつけない場合もある。この場合も衝突しないので "GOOD" を 1 行に出力せよ。

部分点

この問題には、問題を読んでくれたお礼程度の部分点が設定されている。以下の制約を追加で満たすテストケースに正解すれば、1 点が与えられる。

• N = 2

入力例1

5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1

出力例1

GOOD
HIT
HIT
HIT

左が 1,2 つ目の質問の時の様子で、右が 3,4 つ目の質問の時の様子である。

例えば 1 つ目の質問に対しては、 1, 3, 5 を通る経路の一通りしかない。この場合の経路の長さは 7 なので、必ず衝突しない。

7/23 15:40追記 秒ごとの経過を表す。

• 2 秒後、蛙 1 は、葉っぱ 3 に到着。蛙 5 は、葉っぱ 3 から 葉っぱ 5 間の経路で、2 進んだところに存在する。
• 3 秒後、蛙 1(葉っぱ3 から 葉っぱ 5 の経路で 葉っぱ 3 から 1 進んだ場所) と 蛙 5(葉っぱ 3 から 葉っぱ 5 の経路で 葉っぱ 5 から 3 進んだ場所) の距離は 3 となる。
• 4 秒後、蛙 1 と 蛙 5 の距離は 1 となる。
• 5 秒後、蛙 1 と 蛙 5 の位置は 入れ替わる。このとき、着地地点が異なるため衝突しない。

2 つ目の質問に対しては、 2, 1, 3, 5 を通る経路の一通りしかない。この場合の経路の長さは 10 なので葉っぱ 3 で必ず衝突する。

7/23 15:40追記 秒ごとの経過を表す。

• 4 秒後、蛙 2 は 葉っぱ 3 から 葉っぱ 1 側に 1 進んだところに存在し、蛙 5 は 葉 3 から 葉っぱ 5 側に 1 進んだところに存在する。
• 5 秒後、双方の着地地点が 葉 3 で同一のため衝突する。

3 つ目の質問に対しては、 1, 4, 2, 1, 3, 5 を経路とすれば 経路の長さは 20 となり、距離 10 のとき衝突する。

入力例2

5 7
1 1 2 3
1 2 4 4
1 5 3 1
2 1 3 1
2 5 3 1
1 3 1 2
2 3 4 1

出力例2

GOOD
GOOD
GOOD

かえるたちは嬉しい運命だった。

入力例3

3 6
1 1 2 1
1 1 3 3
1 2 3 2
1 2 1 2
2 1 3 1
2 2 3 1

出力例3

HIT
HIT

かえるたちは悲しい運命だった。同じ 2 つの葉っぱ間に複数本の経路が教えられることに注意してください。