Submission #14162619


Source Code Expand

Copy
"""

https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_d

部分永続ufっぽい問題だなぁ

addクエリは分かりやすい→問答無用でくっつける
completeは完全グラフにするよね

最後にcompleteされた時刻が二つの集合がくっついた時刻より
後ならばYes,そうでなければNo

ufの処理を待てばいい?
dictに辺の接続だけ入れておく
qに接続も入れておく

completeが来たら、連結していたところ全部をガンガンufしていく
uf待ちキューを管理するのが大変そう
小さい方をマージすればO(logN)になる?

waの原因は何?
Yes→Noが一番考えられるかな
本来もう繋がってるはずなのに繋がってないと判定されちゃう
"""
def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n

def uf_union(a,b,p,rank):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
        elif rank[ap] < rank[bp]:
            p[ap] = bp
        else:
            p[bp] = ap
            rank[ap] += 1
        return False

def uf_unionX(a,b,p,rank):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:
        if len(rank[ap]) > len(rank[bp]):
            p[bp] = ap
            rank[ap] += rank[bp]
        else:
            p[ap] = bp
            rank[bp] += rank[ap]
        return False


N,Q = map(int,input().split())

p = [i for i in range(N)]
rank = [0] * N

px = [i for i in range(N)]
dic = {}
queue = [ [] for i in range(N) ]

for loop in range(Q):
    t,u,v = map(int,input().split())

    u -= 1
    v -= 1
    if u < v:
        tmp = u
        u = v
        v = tmp

    #print (queue)

    if t == 1:
        
        upx = uf_find(u,px)
        vpx = uf_find(v,px)
        dic[(u,v)] = 1
        queue[upx].append( (u,v) )

        if upx != vpx:
            uf_unionX(vpx,upx,px,queue)

    elif t == 2:

        upx = uf_find(u,px)
        #print (upx)

        for tmp in queue[upx]:

            a,b = tmp
            uf_union(a,b,p,rank)

        queue[upx] = []

    else:

        if (u,v) in dic:
            print ("Yes")
        elif uf_find(u,p) == uf_find(v,p):
            print ("Yes")
        else:
            print ("No")
    

Submission Info

Submission Time
Task D - Propagating Edges
User SPD_9X2
Language PyPy3 (2.4.0)
Score 800
Code Size 2576 Byte
Status
Exec Time 2993 ms
Memory 125600 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2
All 800 / 800 bigrand_0, bigrand_1, bigrand_2, bigrand_3, bigrand_4, comp_0, comp_1, comp_2, comp_3, example_0, example_1, example_2, rand_0, rand_1, rand_10, rand_11, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, randcomp_0, randcomp_1, randcomp_2, randcomp_3, randcomp_4, tenc_0, tenc_1, tenc_2, tenc_3, tree_0, tree_1, tree_2, tree_3
Case Name Status Exec Time Memory
bigrand_0 2818 ms 122912 KB
bigrand_1 2993 ms 124448 KB
bigrand_2 2676 ms 122016 KB
bigrand_3 2883 ms 124832 KB
bigrand_4 2837 ms 124268 KB
comp_0 2367 ms 121376 KB
comp_1 2543 ms 124064 KB
comp_2 2086 ms 96928 KB
comp_3 2100 ms 97952 KB
example_0 171 ms 38256 KB
example_1 171 ms 38256 KB
example_2 168 ms 38256 KB
rand_0 174 ms 38256 KB
rand_1 179 ms 38384 KB
rand_10 176 ms 38256 KB
rand_11 178 ms 38256 KB
rand_2 172 ms 38384 KB
rand_3 176 ms 38256 KB
rand_4 183 ms 38256 KB
rand_5 175 ms 38256 KB
rand_6 175 ms 38256 KB
rand_7 180 ms 38384 KB
rand_8 170 ms 38256 KB
rand_9 179 ms 38256 KB
randcomp_0 2490 ms 111136 KB
randcomp_1 2292 ms 101664 KB
randcomp_2 2384 ms 115360 KB
randcomp_3 2233 ms 105248 KB
randcomp_4 2320 ms 111136 KB
tenc_0 2243 ms 117024 KB
tenc_1 2530 ms 124012 KB
tenc_2 2501 ms 122528 KB
tenc_3 2381 ms 123884 KB
tree_0 2446 ms 125004 KB
tree_1 2312 ms 123552 KB
tree_2 2680 ms 125600 KB
tree_3 2008 ms 91728 KB