kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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になった
しかも速くなってる
メモリ割り当てがなくなったからかな