ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Union-Find木

ABC126 E - 1 or 2

問題 提出コード 解法 を指定してその数字を特定したとします。 すると、はの偶奇に関わらず、自動的に数字が特定できます。 そして、これが連鎖的に続くことになり、 他にが条件に含まれている部分についても自動的に、もう片方が特定されていきます。 ので…

AtCoder Petrozavodsk Contest 001 D - Forest

問題 提出コード 解法 まずは、全ての木を連結にするには、それぞれの木について、頂点を少なくとも1つ選んで連結にする必要があるので、それぞれの木から、最もコストが小さい点を1つずつ選んでおきます。 また、コストを最も少なくして全てを連結にするに…

ABC097 D - Equals

問題 提出コード 解法 と、およびとが交換可能な場合、とは2回の操作で交換可能になります。 このようなことが全てのペアについて言えるので、結局は 入力で与えられるを辺とみなして頂点辺のグラフを作成したときに、最終的に連結な頂点同士はスワップ可能 …

ABC120 D - Decayed Bridges

問題 提出コード 解法 全ての橋が崩れた状態では、どの島からも別の島へ行くことができません。 よって、不便さは、すなわち となります。 ということで、ここから逆に橋を組み立てていき、不便さを後ろから求めていくことにします。 今現在の不便さがで、次…

ABC065 D - Built?

問題 提出コード 解法 考察でごり押したら最小全域木とかいうやつを使っていたみたいです。 初期状態だと辺の可能性が約本あるので、これだと何をするにも不便です。 ですが、実は本程度まで減らすことができます。 個の座標をxについてソートした場合の隣り…

ARC065 D - 連結 / Connectivity

問題 提出コード 解法 UnionFind木を貼ると解ける問題です。 鉄道について、辺をそのままUnionFind木に反映させると、根が同じ都市については、連結であることになります。 道路についても同様です。ということで、まずはUnionFind木を2つ用意し、鉄道と道路…