結果
問題 | No.1352 Three Coins |
ユーザー | marroncastle |
提出日時 | 2021-01-20 22:55:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 4,057 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 77,804 KB |
最終ジャッジ日時 | 2024-12-23 14:35:39 |
合計ジャッジ時間 | 3,176 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
55,524 KB |
testcase_01 | AC | 41 ms
56,020 KB |
testcase_02 | AC | 49 ms
63,200 KB |
testcase_03 | AC | 41 ms
55,908 KB |
testcase_04 | AC | 41 ms
56,300 KB |
testcase_05 | AC | 42 ms
57,476 KB |
testcase_06 | AC | 90 ms
77,396 KB |
testcase_07 | AC | 43 ms
55,916 KB |
testcase_08 | AC | 95 ms
77,372 KB |
testcase_09 | AC | 48 ms
64,348 KB |
testcase_10 | AC | 68 ms
72,748 KB |
testcase_11 | AC | 45 ms
63,396 KB |
testcase_12 | AC | 41 ms
56,224 KB |
testcase_13 | AC | 45 ms
62,832 KB |
testcase_14 | AC | 94 ms
77,156 KB |
testcase_15 | AC | 51 ms
64,824 KB |
testcase_16 | AC | 39 ms
55,360 KB |
testcase_17 | AC | 51 ms
56,448 KB |
testcase_18 | AC | 50 ms
64,948 KB |
testcase_19 | AC | 40 ms
55,572 KB |
testcase_20 | AC | 41 ms
56,756 KB |
testcase_21 | AC | 99 ms
77,232 KB |
testcase_22 | AC | 41 ms
55,452 KB |
testcase_23 | AC | 39 ms
55,500 KB |
testcase_24 | AC | 40 ms
55,672 KB |
testcase_25 | AC | 40 ms
55,304 KB |
testcase_26 | AC | 38 ms
55,520 KB |
testcase_27 | AC | 39 ms
55,624 KB |
testcase_28 | AC | 80 ms
77,416 KB |
testcase_29 | AC | 41 ms
55,488 KB |
testcase_30 | AC | 90 ms
77,804 KB |
testcase_31 | AC | 41 ms
57,424 KB |
testcase_32 | AC | 71 ms
77,264 KB |
testcase_33 | AC | 40 ms
55,804 KB |
testcase_34 | AC | 40 ms
56,444 KB |
testcase_35 | AC | 41 ms
56,084 KB |
ソースコード
import sys input = sys.stdin.readline from collections import deque import heapq class Graph: def __init__(self, N, M=-1): self.V = N if M>=0: self.E = M self.edge = [[] for _ in range(self.V)] self.edge_rev = [[] for _ in range(self.V)] self.order = [] self.to = [0]*self.V self.visited = [False]*self.V self.dp = [0]*self.V def add_edges(self, ind=1, bi=False, rev=False): for i in range(self.E): a,b = map(int, input().split()) a -= ind; b -= ind self.edge[a].append(b) if rev: self.edge_rev[b].append(a) self.to[b] += 1 if bi: self.edge[b].append(a) def add_edge(self, a, b, d, bi=False, rev=False): self.edge[a].append((d, b)) if rev: self.edge_rev[b].append(a) if bi: self.edge[b].append((d, a)) def dfs_rec(self, v): if self.visited[v]: return self.dp[v] for u in self.edge[v]: self.dp[v] += self.dfs_rec(u, v) self.visited[v] = True return self.dp[v] def topo_sort(self): #topological sort updated = [0]*self.V for start in range(self.V): if self.to[start] or updated[start]: continue stack = deque([start]) while stack: v = stack.popleft() self.order.append(v) updated[v] = 1 for u in self.edge[v]: self.to[u] -= 1 if self.to[u]: continue stack.append(u) def dp(self): #トポソしてから # self.dp = [0]*self.V for v in self.order: #行きがけ for u in self.edge[v]: self.dp[u] = max(self.dp[u], self.dp[v]+1) #配るDP for v in self.order[::-1]: #帰りがけ for u in self.edge_rev[v]: self.dp[u] = max(self.dp[u], self.dp[v]+1) #配るDP def bfs(self, start): d = deque([start]) self.min_cost = [-1]*self.V; self.min_cost[start]=0 while len(d)>0: v = d.popleft() for w in self.edge[v]: if self.min_cost[w]==-1: self.min_cost[w]=self.min_cost[v]+1 d.append(w) return #O(ElogV),頂点数10**5以下 def dijkstra_heap(self,s): self.dists = [float('inf')] * self.V; self.dists[s] = 0 used = [False] * self.V; used[s] = True vlist = [] #vlist : [sからの暫定(未確定)最短距離,頂点]のリスト #edge[s] : sから出る枝の[重み,終点]のリスト for e in self.edge[s]: heapq.heappush(vlist,e) #sの隣の点は枝の重さがそのまま暫定最短距離となる while len(vlist): #まだ使われてない頂点の中から最小の距離のものを探す→確定させる d,v = heapq.heappop(vlist) #[d,v]:[sからの(確定)最短距離,頂点] if used[v]: continue self.dists[v] = d; used[v] = True for d,w in self.edge[v]: if not used[w]: heapq.heappush(vlist,(self.dists[v]+d,w)) #O(ElogV),重みが整数の場合のみ def dijkstra_fast(self,s,mod): self.dists = [float('inf')] * self.V; self.dists[s] = 0 #始点sから各頂点への最短距離 used = [False] * self.V; used[s] = True vlist = [] #vlist : [sからの暫定(未確定)最短距離,頂点]のリスト #edge[s] : sから出る枝の[重み,終点]のリスト for w,v in self.edge[s]: heapq.heappush(vlist,w*mod+v) #sの隣の点は枝の重さがそのまま暫定最短距離となる while len(vlist): #まだ使われてない頂点の中から最小の距離のものを探す→確定させる #d, v : sからの(確定)最短距離, 頂点 d,v = divmod(heapq.heappop(vlist),mod) if used[v]: continue self.dists[v] = d; used[v] = True for d,w in self.edge[v]: if not used[w]: heapq.heappush(vlist,(self.dists[v]+d)*mod+w) from math import gcd def multi_gcd(A): g = A[0] for a in A: g = gcd(g,a) return g A = list(map(int, input().split())) if multi_gcd(A)>1: print('INF') exit() A.sort() G = Graph(A[0]) for i in range(A[0]): G.add_edge(i, (i+A[1])%A[0], (i+A[1])//A[0]) G.add_edge(i, (i+A[2])%A[0], (i+A[2])//A[0]) G.dijkstra_heap(0) print(sum(G.dists))