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

ferinの競プロ帳

競プロについてのメモ

ABC049D

abc049.contest.atcoder.jp

自力では手も足も出なかったのでeditorialと解説放送を参考に実装しました。
youtu.be
https://youtu.be/jvAX9Z7beLg

グラフの連結を管理するために、グループ分けを管理するためのデータ構造であるUnion-Find木を使います。
道路での連結を表すUnion-Find木と電車での連結を表すUnion-Find木をそれぞれ用意し管理します。
Union-Find木では連結している頂点同士では根となるノードが同じになります。
よって、道路と電車双方で連結している頂点はその頂点の根がそれぞれ同じとなります。
そのような頂点の数を数えることで両方で連結している頂点数を求めることができます。

GCCとclang間違えてCE出したり、DじゃなくてAに提出したりしてたので本番でやらかさないよう気をつけたい。
あと同じpairを数えるのにcount使ったらTLEだった。よくよく考えたらO(N^2)だし当たり前だった。