結果
問題 | No.2565 はじめてのおつかい |
ユーザー | 👑 Kazun |
提出日時 | 2024-01-21 12:07:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,168 ms / 2,000 ms |
コード長 | 7,464 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 302,512 KB |
最終ジャッジ日時 | 2024-01-21 12:07:49 |
合計ジャッジ時間 | 22,868 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
55,736 KB |
testcase_01 | AC | 39 ms
55,736 KB |
testcase_02 | AC | 39 ms
55,736 KB |
testcase_03 | AC | 1,168 ms
302,492 KB |
testcase_04 | AC | 613 ms
302,512 KB |
testcase_05 | AC | 39 ms
55,736 KB |
testcase_06 | AC | 357 ms
120,368 KB |
testcase_07 | AC | 199 ms
98,508 KB |
testcase_08 | AC | 218 ms
110,736 KB |
testcase_09 | AC | 299 ms
112,800 KB |
testcase_10 | AC | 292 ms
118,256 KB |
testcase_11 | AC | 588 ms
190,836 KB |
testcase_12 | AC | 142 ms
84,748 KB |
testcase_13 | AC | 245 ms
112,128 KB |
testcase_14 | AC | 446 ms
153,132 KB |
testcase_15 | AC | 420 ms
142,548 KB |
testcase_16 | AC | 525 ms
206,196 KB |
testcase_17 | AC | 127 ms
95,864 KB |
testcase_18 | AC | 180 ms
119,580 KB |
testcase_19 | AC | 515 ms
175,204 KB |
testcase_20 | AC | 500 ms
167,052 KB |
testcase_21 | AC | 453 ms
168,140 KB |
testcase_22 | AC | 254 ms
130,536 KB |
testcase_23 | AC | 335 ms
137,216 KB |
testcase_24 | AC | 92 ms
81,984 KB |
testcase_25 | AC | 457 ms
169,524 KB |
testcase_26 | AC | 298 ms
131,228 KB |
testcase_27 | AC | 461 ms
174,044 KB |
testcase_28 | AC | 482 ms
168,892 KB |
testcase_29 | AC | 599 ms
201,364 KB |
testcase_30 | AC | 464 ms
178,948 KB |
testcase_31 | AC | 513 ms
170,420 KB |
testcase_32 | AC | 263 ms
127,608 KB |
testcase_33 | AC | 442 ms
176,300 KB |
testcase_34 | AC | 465 ms
158,852 KB |
testcase_35 | AC | 523 ms
197,156 KB |
testcase_36 | AC | 495 ms
180,236 KB |
testcase_37 | AC | 300 ms
134,968 KB |
testcase_38 | AC | 446 ms
154,644 KB |
testcase_39 | AC | 406 ms
143,272 KB |
testcase_40 | AC | 545 ms
192,764 KB |
testcase_41 | AC | 590 ms
208,672 KB |
testcase_42 | AC | 294 ms
127,612 KB |
testcase_43 | AC | 404 ms
151,380 KB |
testcase_44 | AC | 228 ms
114,304 KB |
testcase_45 | AC | 136 ms
96,712 KB |
testcase_46 | AC | 441 ms
144,920 KB |
testcase_47 | AC | 256 ms
104,428 KB |
testcase_48 | AC | 284 ms
113,312 KB |
testcase_49 | AC | 138 ms
85,004 KB |
testcase_50 | AC | 297 ms
112,308 KB |
testcase_51 | AC | 39 ms
55,736 KB |
testcase_52 | AC | 195 ms
111,092 KB |
ソースコード
class Digraph: """重み[なし]有向グラフを生成する. """ #入力定義 def __init__(self, N=0): """ N 頂点の空グラフを生成する. """ self.arc_number=0 self.adjacent_out=[set() for v in range(N)]#出近傍(vが始点) self.adjacent_in=[set() for v in range(N)] #入近傍(vが終点) #頂点の追加 def add_vertex(self): """ 頂点を追加する. """ self.adjacent_out.append(set()) self.adjacent_in.append(set()) return self.order()-1 def add_vertices(self, k=1): """ 頂点を k 個追加する. k: int """ n=self.order() self.adjacent_out.extend([set() for _ in range(k)]) self.adjacent_in.extend([set() for _ in range(k)]) return list(range(n,n+k)) #辺の追加 def add_arc(self, source, target, mode=0): if target not in self.adjacent_out[source]: self.adjacent_out[source].add(target) self.adjacent_in[target].add(source) self.arc_number+=1 if mode: return self.arc_number-1 else: if mode: return -1 #辺を除く def remove_arc(self, source, target): if target in self.adjacent_out[source]: self.adjacent_out[source].discard(target) self.adjacent_in[target].discard(source) self.arc_number-=1 def reset_vertex(self, u): """ 頂点 u に接続している辺を全て消す.""" X=self.adjacent_out[u].copy() for v in X: self.remove_arc(u,v) X=self.adjacent_in[u].copy() for w in X: self.remove_arc(w,u) #Walkの追加 def add_walk(self,*walk): """ 有向歩道 walk=(w[0], ..., w[n-1]) を追加する. """ N=len(walk) for k in range(N-1): self.add_arc(walk[k],walk[k+1]) #Cycleの追加 def add_cycle(self,*cycle): """ 有向サイクル cycle=(c[0] ..., c[n-1]) を追加する. """ self.add_walk(*cycle) self.add_arc(cycle[-1],cycle[0]) #グラフに辺が存在するか否か def arc_exist(self, u, v): """ 有向辺 u -> v は存在するか? """ return (v in self.adjacent_out[u]) #近傍 def neighbohood(self,v): """vの出近傍, 入近傍を出力する. Input: v:頂点 Output: (出近傍, 入近傍) """ return (self.adjacent_out[v],self.adjacent_in[v]) #出次数 def out_degree(self,v): return len(self.adjacent_out[v]) #入次数 def in_degree(self,v): return len(self.adjacent_in[v]) #次数 def degree(self,v): return (self.out_degree(v),self.in_degree(v)) #相対次数 def relative_degree(self,v): return self.out_degree(v)-self.in_degree(v) #頂点数 def vertex_count(self): """ グラフの頂点数 (位数) を求める.""" return len(self.adjacent_out) def order(self): """ グラフの位数 (頂点数) を求める.""" return len(self.adjacent_out) #辺数 def arc_count(self): """ グラフの辺数 (サイズ) を求める.""" return self.arc_number def size(self): """ グラフのサイズ (辺数) を求める. """ return self.arc_number #頂点vに到達可能な頂点 def reachable_to(self,v): """ 頂点 v に到達可能な頂点を求める. """ from collections import deque N=self.vertex_count() T=[0]*N; T[v]=1 Q=deque([v]) while Q: x=Q.pop() for y in self.adjacent_in[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in range(N) if T[x]] #頂点vから到達可能な頂点 def reachable_from(self,v): """ 頂点 v へ到達可能な頂点を求める. """ from collections import deque N=self.vertex_count() T=[0]*N; T[v]=1 Q=deque([v]) while Q: x=Q.pop() for y in self.adjacent_out[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in range(N) if T[x]] #頂点 u,v の距離を求める. def distance(self,u,v): if u==v: return 0 from collections import deque inf=float("inf") N=self.vertex_count() adj_out=self.adjacent_out T=[inf]*N; T[u]=0 Q=deque([u]) while Q: w=Q.popleft() for x in adj_out[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) if x==v: return T[x] return inf #ある1点からの距離 def distance_all(self,u): """ 頂点 u からの距離を求める.""" from collections import deque inf=float("inf") adj_out=self.adjacent_out T=[inf]*self.vertex_count(); T[u]=0 Q=deque([u]) while Q: w=Q.popleft() for x in adj_out[w]: if T[x]==inf: T[x]=T[w]+1 Q.append(x) return T def shortest_path(self,u,v, dist=False): """ u から v への最短路を求める (存在しない場合は None). dist: False → shortest_path のみ, True → (dist, shortest_path)""" if u==v: if dist: return (0,[u]) else: return [u] from collections import deque inf=float("inf") adj_in=self.adjacent_in T=[-1]*self.vertex_count() Q=deque([v]); T[v]=v while Q: w=Q.popleft() for x in adj_in[w]: if T[x]==-1: T[x]=w Q.append(x) if x==u: P=[u] a=u while a!=v: a=T[a] P.append(a) if dist: return (len(P)-1,P) else: return P if dist: return (inf,None) else: return None #深いコピー def deepcopy(self): from copy import deepcopy D=Digraph(self.vertex_count()) D.arc_number=self.arc_count() D.adjacent_out=deepcopy(self.adjacent_out) D.adjacent_in=deepcopy(self.adjacent_in) return D #================================================== def solve(): N, M = map(int, input().split()) def encode(x, p, q): return (2 * p + q) * N + (x - 1) D = Digraph(4 * N) for j in range(M): u, v = map(int, input().split()) if v == N - 1: a, b = 1, 0 elif v == N: a, b = 0, 1 else: a, b = 0, 0 for p, q in [(0, 0), (0, 1), (1, 0), (1, 1)]: D.add_arc(encode(u, p, q), encode(v, p | a, q | b)) dist = D.distance(encode(1, 0, 0), encode(1, 1, 1)) return dist if dist < float('inf') else -1 #================================================== import sys input=sys.stdin.readline write=sys.stdout.write print(solve())