2820 TN's Kingdom II.100000頂点の Euclidian MST.
Euclidian MST では,MSTの辺は必ずDelauney三角形分割の辺になっていることを利用する.Delauney三角形分割は O(n log n) の確率的アルゴリズムが存在するので,まずDelauney三角形分割を求めてからその上でMSTを解くことでO(n log n) で解ける.
ここまで実装するのでも大変なのに,メモリが足りないという罠に.手元でテストケースを生成して実験してみたところ128MBあれば足りるのだけど,問題の要求は64MB.クラスを配列にしたり,ラッパークラスをプリミティブを使って自分で書き直したりすれば収まるのかもしれないけれど,正直やる気が起きない...
追記
メモリ足りないよと掲示板に書いたらfrkstyc氏(中の人)がメモリ容量を増やしてくださったようです.でも今度はTLE...