結果
問題 | No.3 ビットすごろく |
ユーザー | 👑 Kazun |
提出日時 | 2020-08-19 22:31:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 224 ms / 5,000 ms |
コード長 | 4,725 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 87,172 KB |
実行使用メモリ | 85,652 KB |
最終ジャッジ日時 | 2023-09-14 01:49:08 |
合計ジャッジ時間 | 7,202 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 93 ms
71,620 KB |
testcase_01 | AC | 91 ms
71,628 KB |
testcase_02 | AC | 93 ms
71,644 KB |
testcase_03 | AC | 171 ms
80,192 KB |
testcase_04 | AC | 115 ms
78,080 KB |
testcase_05 | AC | 193 ms
83,148 KB |
testcase_06 | AC | 164 ms
80,208 KB |
testcase_07 | AC | 154 ms
80,204 KB |
testcase_08 | AC | 181 ms
81,756 KB |
testcase_09 | AC | 193 ms
83,548 KB |
testcase_10 | AC | 210 ms
84,640 KB |
testcase_11 | AC | 197 ms
82,776 KB |
testcase_12 | AC | 189 ms
82,620 KB |
testcase_13 | AC | 159 ms
80,148 KB |
testcase_14 | AC | 202 ms
83,764 KB |
testcase_15 | AC | 214 ms
85,652 KB |
testcase_16 | AC | 211 ms
85,376 KB |
testcase_17 | AC | 216 ms
85,608 KB |
testcase_18 | AC | 152 ms
80,660 KB |
testcase_19 | AC | 216 ms
85,540 KB |
testcase_20 | AC | 107 ms
77,840 KB |
testcase_21 | AC | 93 ms
71,540 KB |
testcase_22 | AC | 203 ms
83,980 KB |
testcase_23 | AC | 213 ms
85,620 KB |
testcase_24 | AC | 219 ms
85,544 KB |
testcase_25 | AC | 224 ms
85,428 KB |
testcase_26 | AC | 96 ms
71,628 KB |
testcase_27 | AC | 165 ms
80,040 KB |
testcase_28 | AC | 210 ms
85,356 KB |
testcase_29 | AC | 194 ms
82,768 KB |
testcase_30 | AC | 94 ms
71,672 KB |
testcase_31 | AC | 96 ms
71,720 KB |
testcase_32 | AC | 191 ms
82,532 KB |
ソースコード
class Digraph: #入力定義 def __init__(self,vertex=[]): self.vertex=set(vertex) self.edge_number=0 self.vertex_number=len(vertex) self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点) self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点) #頂点の追加 def add_vertex(self,*adder): for v in adder: if v not in self.vertex: self.adjacent_in[v]={} self.adjacent_out[v]={} self.vertex_number+=1 self.vertex.add(v) #辺の追加(更新) def add_edge(self,From,To,weight=1): for v in [From,To]: if v not in self.vertex: self.add_vertex(v) if To not in self.adjacent_in[From]: self.edge_number+=1 self.adjacent_out[From][To]=weight self.adjacent_in[To][From]=weight #辺を除く def remove_edge(self,From,To): for v in [From,To]: if v not in self.vertex: self.add_vertex(w) if To in self.adjacent_out[From]: del self.adjacent_out[From][To] del self.adjacent_in[To][From] self.edge_number-=1 #頂点を除く def remove_vertex(self,*vertexes): for v in vertexes: if v in self.vertex: self.vertex_number-=1 for u in self.adjacent_out[v]: del self.adjacent_in[u][v] self.edge_number-=1 del self.adjacent_out[v] for u in self.adjacent_in[v]: del self.adjacent_out[u][v] self.edge_number-=1 del self.adjacent_in[v] #Walkの追加 def add_walk(self,*walk): pass #Cycleの追加 def add_cycle(self,*cycle): pass #頂点の交換 def __vertex_swap(self,p,q): self.vertex.sort() #グラフに頂点が存在するか否か def vertex_exist(self,v): return v in self.vertex #グラフに辺が存在するか否か def edge_exist(self,From,To): if not(self.vertex_exist(From) and self.vertex_exist(To)): return False return To in self.adjacent_out[From] #近傍 def neighbohood(self,v): if not self.vertex_exist(v): return [] return list(self.adjacent[v]) #出次数 def out_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_out[v]) #入次数 def in_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_in[v]) #次数 def degree(self,v): if not self.vertex_exist(v): return 0 return self.out_degree(v)-self.in_degree(v) #頂点数 def vertex_count(self): return len(self.vertex) #辺数 def edge_count(self): return self.edge_number #頂点vを含む連結成分 def connected_component(self,v): pass #================================================ #Dijkstra def Dijkstra(D,From,To,with_path=False): """Dijksta法を用いて,FromからToまでの距離を求める. D:辺の重みが全て非負の有向グラフ From:始点 To:終点 with_path:最短路も含めて出力するか? (出力の結果) with_path=True->(距離,最短経路の辿る際の前の頂点) with_path=False->距離 """ from copy import copy from heapq import heappush,heappop T={v:float("inf") for v in D.vertex} T[From]=0 if with_path: Prev={v:None for v in D.vertex} Q=[(0,From)] Flag=False while Q: c,u=heappop(Q) if u==To: Flag=True break if T[u]<c: continue for v in D.adjacent_out[u]: if T[v]>T[u]+D.adjacent_out[u][v]: T[v]=T[u]+D.adjacent_out[u][v] heappush(Q,(T[v],v)) if with_path: Prev[v]=u if not Flag: if with_path: return (float("inf"),None) else: return float("inf") if with_path: path=[To] u=To while (Prev[u]!=None): u=Prev[u] path.append(u) return (T[To],path[::-1]) else: return T[To] #================================================ N=int(input()) D=Digraph(list(range(1,N+1))) for i in range(1,N+1): x=bin(i).count("1") if 1<=i-x: D.add_edge(i,i-x) if i+x<=N: D.add_edge(i,i+x) dist=Dijkstra(D,1,N) if dist==float("inf"): print(-1) else: print(dist+1)