読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ1330 Never Wait for Weights

とても面白いと思ったけど、帰着によってはそうでもないらしい?

問題

Never Wait for Weights | Aizu Online Judge

N個のアイテムがある。M個のクエリが与えられる。クエリは次の2種類である。

  • ! a b w アイテムa, bの重さの差はwである(w_b - w_a = w)
  • ? a b アイテムa, bの重さの差は?(w_b - w_a = ?)

クエリは時系列順に与えられる。各?クエリについて、それまでに得られた!クエリの情報のみから答えが確定できる場合は答えを出力せよ。確定できないときは"UNKNOWN"と出力せよ。

制約

2 <= N <= 100000

1 <= M <= 100000

!クエリは矛盾しない

解法

アイテムを頂点とするグラフを考えます。クエリ! a b wに対し、aからbの向きに重みwの辺を、bからaに重み-wの辺を張ることにすると、? c dの答えが確定できるのはそれまでの!クエリのみによってcとdが連結になっている場合で、答えはcからdまでの距離(有向パス上に含まれる辺の重みの総和)です。!クエリは矛盾しないことが保証されているので、cからdへのパスが複数ある場合、それらのパスが表す距離はすべて等しくなります。そこで、!クエリを処理するとき、辺の両端が既に同じ連結成分に属していれば辺を追加しないことにします。

上のようにすべての!クエリを処理した後のグラフは森になります。? a bに対し、aとbが同じ連結成分に属しているかどうかは前からUnionFindしていけばわかります。aからbまでの距離は、各連結成分が木なのでLCAを使うと高速に求められます。実装上は、すべての木をまとめて扱うためにスーパールートsをつくり、各連結成分から1つずつ頂点を選んでsとの間にコスト0の辺を両向きに張りました。これで全体が木となります。ただしsをまたがないと行き来できないような頂点どうしは連結とはみなさないことにします。

LCAの内部でdfsしたらセグフォしたのでbfsにしました。

gist.github.com