#732274 (PyPy3) No.1805 Approaching Many Typhoon

• 問題: No.1805 Approaching Many Typhoon
• ユーザー: MasKoaTS
• 提出日時: 2022-01-20 21:57:39
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 161 ms / 2,000 ms
• コード長: 2,383 bytes
• コンパイル時間: 165 ms
• コンパイル使用メモリ: 82,688 KB
• 実行使用メモリ: 89,728 KB
• 最終ジャッジ日時: 2024-11-24 07:04:25
• 合計ジャッジ時間: 7,317 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 35

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import itertools as iter
import collections as coll
import heapq as hq
import bisect as bis
from decimal import Decimal as dec
from copy import deepcopy as dcopy
import math
import sys
sys.setrecursionlimit(10**6)
def input():
    return sys.stdin.readline().rstrip()
def getN():
    return int(sys.stdin.readline())
def getNs():
    return map(int,sys.stdin.readline().split())
def getList():
    return list(map(int,sys.stdin.readline().split()))
def strinps(n):
    return [sys.stdin.readline().rstrip() for _ in range(n)]
pi = 3.141592653589793
mod = 10**9+7
MOD = 998244353
INF = math.inf
dx = [1,0,-1,0];    dy = [0,1,0,-1]
"""
Union-Find
from : https://github.com/customaddone/beginPython/blob/master/cgi-bin/library/unionfind/unionfind.py
ref : https://algo-logic.info/union-find-tree/
"""
class UnionFind():
    #Uni = UnionFind(n) のようにする
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    #xの親（親がいないときは自身の番号を返す）
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    #xとyを関係付ける
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        # if x > y: # よりrootのインデックスが小さい方が親
            # x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    #xとyが同じ組に属するかどうか
    def same(self, x, y):
        return self.find(x) == self.find(y)
    #xが属する組の大きさ
    def size(self, x):
        return -self.parents[self.find(x)]
    #xが属する組の全要素をリストとして取得
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    #Union-Find木の根に当たる要素全てをリストとして取得
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    #Union-Find木の根とそれに属する組の全要素
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
"""
Main Code
"""
n, m = getNs()
s, g = [i - 1 for i in getNs()]
ship = [[i - 1 for i in getNs()] for _ in [0] * m]
t = getN()
st = set(i - 1 for i in getNs())
uni = UnionFind(n)
for a, b in ship:
    if(a not in st and b not in st):
        uni.union(a, b)
if(uni.same(s, g)):
    print("Yes")
else:
    print("No")
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX