結果

問題 No.2316 Freight Train
コンテスト
ユーザー june19312
提出日時 2023-05-27 13:18:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 814 ms / 2,000 ms
コード長 2,271 bytes
コンパイル時間 846 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 140,800 KB
最終ジャッジ日時 2024-12-25 22:52:18
合計ジャッジ時間 20,727 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#=======Union-Find==========

#頂点数に合わせて初期化
#問題に合わせて要変更

root = [0]*(N+1)
UFsize = [1]*(N+1)
UFdict = {}

for i,v in enumerate(root):
    root[i] = i
    UFdict[i] = 1

#ある頂点の根を求めて返す
#途中通過した頂点は同じ根につなぎ直す

def find(x):
    rootlist = []
    UFX = x
    UFflag = True
        
    while UFflag:
        if root[UFX] == UFX:
            UFflag = False
            break
        else:
            rootlist.append(UFX)
            UFX = root[UFX]

    if len(rootlist) >= 1:
        for jj in rootlist:
            root[jj] = UFX
    
    return UFX

#ある頂点とある頂点をつなぐ
#頂点の数字の若い方が優先される

def union(x,y):
    xx = find(x)
    yy = find(y)
    if xx == yy:
        return
    else:
        if xx<yy:
            root[yy] = xx
            UFsize[xx]+=UFsize[yy]
            UFsize[yy] = 0
            del UFdict[yy]
            return
        else:
            root[xx] = yy
            UFsize[yy]+=UFsize[xx]
            UFsize[xx] = 0
            del UFdict[xx]
            return

#ある頂点とある頂点が同じ根に属するかを
#True or Falseで返す

def same(x,y):
    return find(x) == find(y)

#ある頂点と同じグループに属する頂点の数を返す

def size(x):
    return UFsize[find(x)]

#現在の連結成分の数を返す
#1-indexedで初期化しているので問題によっては
#インデックス0を含める分1多く出力される

def groups():
    return len(UFdict)

#Unionの結果、Union-Find木が深くなってしまうことがある。
#配列rootの中身を見て考察する際に困ることが多いため、
#全頂点をfindして根につなぎ直す。
#主に考察用の作業。ただし答えを出力するのにrootを使う場合は
#必須の作業となる。

def update_root():
    for ufi in range(N+1):
        find(ufi)

#=======Union-Findここまで==========

for i,v in enumerate(P):
    if v == -1:
        continue
    
    union(i+1,v)

for i in range(Q):
    A,B = map(int,input().split())
    if same(A,B):
        print("Yes")
    else:
        print("No")
0