結果

問題 No.2316 Freight Train
ユーザー june19312june19312
提出日時 2023-05-27 13:18:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 861 ms / 2,000 ms
コード長 2,271 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 87,280 KB
実行使用メモリ 141,336 KB
最終ジャッジ日時 2023-08-26 20:40:10
合計ジャッジ時間 23,006 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
71,256 KB
testcase_01 AC 64 ms
71,352 KB
testcase_02 AC 66 ms
71,404 KB
testcase_03 AC 748 ms
141,336 KB
testcase_04 AC 526 ms
106,900 KB
testcase_05 AC 372 ms
106,940 KB
testcase_06 AC 252 ms
80,368 KB
testcase_07 AC 686 ms
88,592 KB
testcase_08 AC 557 ms
113,524 KB
testcase_09 AC 677 ms
115,344 KB
testcase_10 AC 643 ms
106,820 KB
testcase_11 AC 665 ms
134,428 KB
testcase_12 AC 735 ms
129,012 KB
testcase_13 AC 847 ms
113,712 KB
testcase_14 AC 861 ms
113,720 KB
testcase_15 AC 832 ms
113,760 KB
testcase_16 AC 859 ms
113,540 KB
testcase_17 AC 852 ms
113,564 KB
testcase_18 AC 747 ms
113,880 KB
testcase_19 AC 722 ms
113,820 KB
testcase_20 AC 761 ms
113,644 KB
testcase_21 AC 755 ms
113,624 KB
testcase_22 AC 710 ms
113,964 KB
testcase_23 AC 567 ms
113,380 KB
testcase_24 AC 627 ms
113,532 KB
testcase_25 AC 530 ms
139,880 KB
testcase_26 AC 512 ms
139,744 KB
testcase_27 AC 447 ms
78,036 KB
testcase_28 AC 65 ms
70,936 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