#993508 (PyPy3) No.2780 The Bottle Imp

提出ソース

結果

問題	No.2780 The Bottle Imp
ユーザー	のーと
提出日時	2024-07-10 15:41:11
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	1,676 bytes
コンパイル時間	382 ms
コンパイル使用メモリ	81,884 KB
実行使用メモリ	87,684 KB
最終ジャッジ日時	2024-07-10 15:41:21
合計ジャッジ時間	6,783 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	39 ms 54,460 KB
testcase_01	AC	45 ms 53,984 KB
testcase_02	AC	38 ms 54,148 KB
testcase_03	AC	39 ms 54,520 KB
testcase_04	AC	38 ms 54,048 KB
testcase_05	AC	37 ms 55,308 KB
testcase_06	AC	46 ms 54,452 KB
testcase_07	AC	137 ms 81,396 KB
testcase_08	AC	156 ms 82,588 KB
testcase_09	AC	134 ms 81,668 KB
testcase_10	AC	161 ms 82,812 KB
testcase_11	AC	129 ms 81,612 KB
testcase_12	AC	152 ms 85,452 KB
testcase_13	AC	157 ms 85,464 KB
testcase_14	AC	106 ms 78,120 KB
testcase_15	AC	85 ms 78,460 KB
testcase_16	AC	85 ms 78,272 KB
testcase_17	AC	95 ms 78,260 KB
testcase_18	AC	86 ms 78,284 KB
testcase_19	AC	94 ms 78,240 KB
testcase_20	AC	91 ms 78,332 KB
testcase_21	AC	86 ms 78,216 KB
testcase_22	AC	120 ms 79,180 KB
testcase_23	AC	94 ms 78,064 KB
testcase_24	AC	141 ms 81,480 KB
testcase_25	AC	189 ms 83,772 KB
testcase_26	AC	124 ms 80,244 KB
testcase_27	AC	121 ms 84,704 KB
testcase_28	AC	117 ms 84,588 KB
testcase_29	WA	-
testcase_30	AC	106 ms 80,876 KB
testcase_31	AC	168 ms 87,608 KB
testcase_32	AC	65 ms 77,160 KB
testcase_33	AC	159 ms 87,684 KB
testcase_34	AC	181 ms 87,588 KB
testcase_35	AC	69 ms 76,992 KB
testcase_36	WA	-
testcase_37	WA	-
testcase_38	AC	72 ms 76,988 KB
testcase_39	AC	133 ms 85,272 KB
testcase_40	AC	140 ms 85,256 KB
testcase_41	WA	-
testcase_42	AC	43 ms 54,824 KB
testcase_43	AC	39 ms 55,836 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

N=int(input())

def minus1(L):#入力前に
  return [l-1 for l in L]
def emp_graph(N):#長さNの空の隣接リスト
  return [[] for i in range(N)]
 
graph=emp_graph(N)
  
for i in range(N):
	L=minus1(list(map(int,input().split())))
	M=L[0]
	A=L[1:]
	for a in A:
		graph[i].append(a)

#print(graph)

from collections import deque
import sys
sys.setrecursionlimit(7*10**5) #ここまでは共通
def bfs(graph,start):#隣接リストgraphの頂点startから各点までの最短距離(デフォ-1)のリストdistを返す
  """
  各辺がつなぐ2つの頂点をa,bとする
  →隣接リストgraphにa→bなど入れる
  ※有向グラフなら片方から、無向グラフなら両側から入れる
  """
  dist = [-1]*len(graph) #各頂点の最短距離のリスト(これが求めるもの。デフォは-1)
  dist[start] = 0 #最初の出発地は0にする
  d=deque()
  d.append(start) #最初の出発地を入れる
  
  """
  目的地になったが出発地になっていない頂点のdeque
  「先頭から要素を取り出す」「末尾に要素を追加する」ためdeque使用
  """
  
  while len(d)>0: # (出発地,目的地)
   i = d.popleft() #dの一番[左]は今から出発地になる
   for j in graph[i]: #その頂点に直接つながる各頂点[目]について
     if dist[j] != -1: #[目]に訪問済みなら
       continue #スキップ
     dist[j] = dist[i] + 1 #でなければ(未訪問なら直ちに)最短距離をdistに記録（目的地になった）
     d.append(j) #dの[右]に、出発地未経験の頂点を追加
  return dist

dist=bfs(graph,0)#普通の場合
print("No" if -1 in dist else "Yes")

yukicoder

結果

テストケース

ソースコード