DSL_1_A:Disjoint Set: Union Find Tree (続き)
70000コマンド(#31)でTLE
これはアルゴリズムの問題だろうか
stdinから読んだら早くなるかなと思ってこうしたり
for _ in range(q):
com, x, y = [int(x) for x in stdin.readline().split()]
こうしたりしてみたけどあまり変わらず
lines = stdin.readlines()
for line in lines:
com, x, y = [int(x) for x in line.split()]
やっぱりアルゴリズムの問題かなあ
sameが呼ばれる回数が多いなら、先祖のポインタを置き換えるだけじゃなくて、
同じ集合の要素が直接親ポインタを指すように書き換えたほうが速いかも知れないけど
あんまりありそうな気がしない
あ、ancestorをキャッシュしておいたらどうかな
更新される可能性はあるけど、キャッシュされたところから上にたどり直せばいいはず
修正もきっとそれほどでもないのでは
ほら
class DisjointSet():
def __init__(self):
self.parent = None
self.ancestor = self
def ancestor(elems, x):
s = elems[x].ancestor
while s.parent is not None:
s = s.parent
elems[x].ancestor = s
return s
ほらAC
あ、木が深くなると遅くなると思ってやってなかったけど、
どうせ先祖をキャッシュするんなら
新しく親を作るのではなくてどっちかを親にすればメモリが節約できるな
さっきは#31でメモリを9020KB使ってたのが最大
どっちが親になるかだけど先祖をキャッシュしてあるからどっちでも大差はなかろう
そうするとヒントの絵と同じ形になるのかな
親につなぐときに先祖もコピーしておくといいだろう
こう
def unite(elems, x, y):
ax = ancestor(elems, x)
ay = ancestor(elems, y)
if ax is not ay:
ax.parent = ay
ax.ancestor = ay.ancestor
7364 KBになった
しかも速くなってる
メモリ割り当てがなくなったからかな