結果

問題 No.2316 Freight Train
ユーザー june19312june19312
提出日時 2023-05-27 13:18:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 781 ms / 2,000 ms
コード長 2,271 bytes
コンパイル時間 638 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 140,904 KB
最終ジャッジ日時 2024-06-07 16:10:07
合計ジャッジ時間 19,339 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,224 KB
testcase_01 AC 37 ms
52,096 KB
testcase_02 AC 39 ms
52,608 KB
testcase_03 AC 739 ms
140,160 KB
testcase_04 AC 442 ms
105,456 KB
testcase_05 AC 371 ms
105,384 KB
testcase_06 AC 219 ms
78,208 KB
testcase_07 AC 607 ms
87,160 KB
testcase_08 AC 491 ms
140,904 KB
testcase_09 AC 587 ms
114,312 KB
testcase_10 AC 613 ms
105,216 KB
testcase_11 AC 554 ms
133,376 KB
testcase_12 AC 637 ms
128,356 KB
testcase_13 AC 740 ms
140,644 KB
testcase_14 AC 764 ms
140,800 KB
testcase_15 AC 765 ms
140,472 KB
testcase_16 AC 758 ms
140,768 KB
testcase_17 AC 730 ms
140,492 KB
testcase_18 AC 781 ms
140,288 KB
testcase_19 AC 749 ms
140,544 KB
testcase_20 AC 779 ms
140,524 KB
testcase_21 AC 763 ms
140,496 KB
testcase_22 AC 769 ms
140,500 KB
testcase_23 AC 612 ms
140,288 KB
testcase_24 AC 678 ms
140,540 KB
testcase_25 AC 587 ms
138,368 KB
testcase_26 AC 520 ms
138,368 KB
testcase_27 AC 456 ms
76,416 KB
testcase_28 AC 37 ms
52,224 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