結果

問題 No.2316 Freight Train
ユーザー june19312june19312
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
51,968 KB
testcase_01 AC 38 ms
51,968 KB
testcase_02 AC 38 ms
51,840 KB
testcase_03 AC 737 ms
140,288 KB
testcase_04 AC 482 ms
105,344 KB
testcase_05 AC 376 ms
105,088 KB
testcase_06 AC 227 ms
77,952 KB
testcase_07 AC 615 ms
87,296 KB
testcase_08 AC 503 ms
140,544 KB
testcase_09 AC 587 ms
114,176 KB
testcase_10 AC 655 ms
105,344 KB
testcase_11 AC 591 ms
133,632 KB
testcase_12 AC 687 ms
128,000 KB
testcase_13 AC 795 ms
140,672 KB
testcase_14 AC 786 ms
140,416 KB
testcase_15 AC 780 ms
140,544 KB
testcase_16 AC 814 ms
140,544 KB
testcase_17 AC 767 ms
140,544 KB
testcase_18 AC 787 ms
140,800 KB
testcase_19 AC 771 ms
140,288 KB
testcase_20 AC 810 ms
140,544 KB
testcase_21 AC 776 ms
140,288 KB
testcase_22 AC 772 ms
140,544 KB
testcase_23 AC 622 ms
140,672 KB
testcase_24 AC 653 ms
140,288 KB
testcase_25 AC 559 ms
138,240 KB
testcase_26 AC 575 ms
138,752 KB
testcase_27 AC 471 ms
76,032 KB
testcase_28 AC 40 ms
51,712 KB
権限があれば一括ダウンロードができます

ソースコード

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