結果
問題 | No.1805 Approaching Many Typhoon |
ユーザー | MasKoaTS |
提出日時 | 2022-01-20 21:57:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 2,383 bytes |
コンパイル時間 | 927 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 89,728 KB |
最終ジャッジ日時 | 2024-05-03 08:36:11 |
合計ジャッジ時間 | 7,536 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 128 ms
86,400 KB |
testcase_01 | AC | 130 ms
86,368 KB |
testcase_02 | AC | 131 ms
86,136 KB |
testcase_03 | AC | 126 ms
85,888 KB |
testcase_04 | AC | 134 ms
86,528 KB |
testcase_05 | AC | 128 ms
86,164 KB |
testcase_06 | AC | 132 ms
86,272 KB |
testcase_07 | AC | 131 ms
86,272 KB |
testcase_08 | AC | 130 ms
86,516 KB |
testcase_09 | AC | 129 ms
86,272 KB |
testcase_10 | AC | 132 ms
86,312 KB |
testcase_11 | AC | 133 ms
85,888 KB |
testcase_12 | AC | 132 ms
86,272 KB |
testcase_13 | AC | 131 ms
86,272 KB |
testcase_14 | AC | 134 ms
86,400 KB |
testcase_15 | AC | 134 ms
86,272 KB |
testcase_16 | AC | 129 ms
86,144 KB |
testcase_17 | AC | 130 ms
86,272 KB |
testcase_18 | AC | 130 ms
86,272 KB |
testcase_19 | AC | 130 ms
86,400 KB |
testcase_20 | AC | 131 ms
86,400 KB |
testcase_21 | AC | 130 ms
86,144 KB |
testcase_22 | AC | 130 ms
86,272 KB |
testcase_23 | AC | 131 ms
86,144 KB |
testcase_24 | AC | 128 ms
86,400 KB |
testcase_25 | AC | 130 ms
86,400 KB |
testcase_26 | AC | 130 ms
86,272 KB |
testcase_27 | AC | 131 ms
86,272 KB |
testcase_28 | AC | 147 ms
89,600 KB |
testcase_29 | AC | 147 ms
89,728 KB |
testcase_30 | AC | 149 ms
89,600 KB |
testcase_31 | AC | 145 ms
89,676 KB |
testcase_32 | AC | 130 ms
86,460 KB |
testcase_33 | AC | 131 ms
86,016 KB |
testcase_34 | AC | 137 ms
86,472 KB |
testcase_35 | AC | 140 ms
88,960 KB |
testcase_36 | AC | 143 ms
89,216 KB |
testcase_37 | AC | 130 ms
86,312 KB |
testcase_38 | AC | 129 ms
86,272 KB |
ソースコード
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")