Submission #14162341


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)になる?

"""
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[bp] += rank[ap]
        else:
            p[bp] = ap
            rank[ap] += rank[bp]
        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)

        if upx != vpx:
            dic[(u,v)] = 1
            queue[upx].append( (upx,vpx) )
            #print (vpx,upx,queue)
            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 0
Code Size 2476 Byte
Status
Exec Time 3213 ms
Memory 892364 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2
All 0 / 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 2776 ms 124832 KB
bigrand_1 2796 ms 128032 KB
bigrand_2 2486 ms 122892 KB
bigrand_3 2491 ms 122272 KB
bigrand_4 2668 ms 124140 KB
comp_0 2217 ms 118608 KB
comp_1 2270 ms 126880 KB
comp_2 2129 ms 115616 KB
comp_3 1895 ms 93472 KB
example_0 172 ms 38256 KB
example_1 171 ms 39116 KB
example_2 162 ms 38256 KB
rand_0 168 ms 38256 KB
rand_1 173 ms 38256 KB
rand_10 179 ms 38256 KB
rand_11 175 ms 38256 KB
rand_2 172 ms 38256 KB
rand_3 168 ms 38256 KB
rand_4 185 ms 38256 KB
rand_5 168 ms 38256 KB
rand_6 178 ms 38256 KB
rand_7 178 ms 38256 KB
rand_8 165 ms 38256 KB
rand_9 168 ms 38256 KB
randcomp_0 2382 ms 125644 KB
randcomp_1 3213 ms 886648 KB
randcomp_2 2425 ms 124320 KB
randcomp_3 3210 ms 892364 KB
randcomp_4 2514 ms 125216 KB
tenc_0 2316 ms 122204 KB
tenc_1 2350 ms 123628 KB
tenc_2 2404 ms 125472 KB
tenc_3 2411 ms 124960 KB
tree_0 2304 ms 124192 KB
tree_1 2141 ms 115360 KB
tree_2 2533 ms 124448 KB
tree_3 2072 ms 109772 KB