結果

問題 No.2316 Freight Train
ユーザー kyskys
提出日時 2023-05-26 21:25:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 773 ms / 2,000 ms
コード長 2,313 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 109,824 KB
最終ジャッジ日時 2024-12-25 04:36:31
合計ジャッジ時間 16,379 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    from sys import stdin, setrecursionlimit
    # setrecursionlimit(1000000)
    input = stdin.readline
    def iinput(): return int(input())
    def sinput(): return input().rstrip()
    def i0input(): return int(input()) - 1
    def linput(): return list(input().split())
    def liinput(): return list(map(int, input().split()))
    def miinput(): return map(int, input().split())
    def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
    def mi0input(): return map(lambda x: int(x) - 1, input().split())
    INF = 1000000000000000000
    MOD = 1000000007

    class UnionFindTree:
        def __init__(self, initial_size:int) -> None:
            self.n_nodes = initial_size
            self.parents = [i for i in range(initial_size)]
            self.ranks = [0 for i in range(initial_size)]
            self.size = [1 for i in range(initial_size)]
            self.n_roots = initial_size
        def root(self, n:int) -> int:
            if self.parents[n] == n:
                return n
            else:
                self.parents[n] = self.root(self.parents[n])
                return self.parents[n]
        def same(self, n:int, m:int) -> bool:
            return (self.root(n) == self.root(m))
        def unite(self, n:int, m:int) -> None:
            if self.same(n, m):
                return
            self.n_roots -= 1
            n, m = self.root(n), self.root(m)
            if self.ranks[n] < self.ranks[m]:
                self.parents[n] = m
                self.size[m] += self.size[n]
            else:
                self.parents[m] = n
                self.size[n] += self.size[m]
                if self.ranks[n] == self.ranks[m]:
                    self.ranks[n] += 1
        def get_roots(self) -> set:
            return set([self.root(x) for x in range(self.n_nodes)])
        def count_roots(self) -> int:
            return self.n_roots
        def get_tree_size(self, n:int) -> int:
            return self.size[self.root(n)]

    N, Q = miinput()
    uf = UnionFindTree(N)

    P = li0input()

    for i, p in enumerate(P):
        if p == -2:
            continue
        uf.unite(i, p)
    
    for _ in [0] * Q:
        a, b = mi0input()
        if uf.same(a, b):
            print('Yes')
        else:
            print('No')

main()
0