Submission #14162382


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[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)

        if upx != vpx:
            dic[(u,v)] = 1
            queue[upx].append( (u,v) )
            #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 2472 Byte
Status
Exec Time 2966 ms
Memory 125984 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 2798 ms 125088 KB
bigrand_1 2966 ms 124576 KB
bigrand_2 2658 ms 122144 KB
bigrand_3 2796 ms 124832 KB
bigrand_4 2829 ms 124332 KB
comp_0 2285 ms 120352 KB
comp_1 2421 ms 125984 KB
comp_2 2106 ms 99104 KB
comp_3 1997 ms 96012 KB
example_0 177 ms 38256 KB
example_1 169 ms 38256 KB
example_2 171 ms 38256 KB
rand_0 174 ms 38256 KB
rand_1 171 ms 38256 KB
rand_10 177 ms 38384 KB
rand_11 170 ms 38256 KB
rand_2 174 ms 38256 KB
rand_3 173 ms 38256 KB
rand_4 172 ms 38256 KB
rand_5 178 ms 38384 KB
rand_6 173 ms 38256 KB
rand_7 176 ms 38256 KB
rand_8 170 ms 38256 KB
rand_9 177 ms 38256 KB
randcomp_0 2390 ms 111136 KB
randcomp_1 2184 ms 101664 KB
randcomp_2 2393 ms 115360 KB
randcomp_3 2253 ms 105120 KB
randcomp_4 2403 ms 111136 KB
tenc_0 2152 ms 114720 KB
tenc_1 2413 ms 124396 KB
tenc_2 2449 ms 125984 KB
tenc_3 2374 ms 123116 KB
tree_0 2286 ms 124064 KB
tree_1 2169 ms 116980 KB
tree_2 2478 ms 124704 KB
tree_3 2146 ms 111264 KB