結果
問題 | No.1607 Kth Maximum Card |
ユーザー | ああいい |
提出日時 | 2022-03-07 11:31:20 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,297 bytes |
コンパイル時間 | 257 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 136,320 KB |
最終ジャッジ日時 | 2024-07-22 05:05:25 |
合計ジャッジ時間 | 22,790 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
54,272 KB |
testcase_01 | AC | 44 ms
53,888 KB |
testcase_02 | WA | - |
testcase_03 | AC | 44 ms
54,656 KB |
testcase_04 | WA | - |
testcase_05 | AC | 43 ms
54,400 KB |
testcase_06 | AC | 44 ms
54,016 KB |
testcase_07 | AC | 46 ms
53,888 KB |
testcase_08 | AC | 2,018 ms
132,556 KB |
testcase_09 | AC | 1,532 ms
124,932 KB |
testcase_10 | AC | 1,967 ms
136,320 KB |
testcase_11 | AC | 310 ms
87,552 KB |
testcase_12 | AC | 1,460 ms
120,788 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 173 ms
83,712 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 1,050 ms
124,024 KB |
testcase_23 | AC | 1,053 ms
123,900 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 1,094 ms
106,712 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 216 ms
97,792 KB |
testcase_35 | WA | - |
ソースコード
import sysrr = sys.stdinN,M,K = map(int,rr.readline().split())G = [[] for _ in range(N+1)]for _ in range(M):a,b,c = map(int,rr.readline().split())G[a].append((b,c))G[b].append((a,c))import heapqinf = 10 ** 6base = 23mask = (1 << base) - 1"""def calc(x):dist = [K] * (N+1)dist[1] = 0q = [1]while q:u = heapq.heappop(q)d,now = u >> base,u & maskif now == N:breakif dist[now] < d:continuefor v,c in G[now]:if c > x:c = 1else:c = 0if dist[v] > d + c:dist[v] = d + cheapq.heappush(q,(d+c) << base | v)return dist[N] < K"""from collections import dequedef calc(x):dist = [-1] * (N+1)dist[1] = 0q = deque([1])while q:now = q.popleft()for v,c in G[now]:if dist[v] >= 0:continueif c > x:dist[v] = dist[now] + 1q.append(v)else:dist[v] = dist[now]q.appendleft(v)return dist[N] < Kstart = -1end = 2 * 10 ** 5while end - start > 1:mid = (end + start) // 2if calc(mid):end = midelse:start = midprint(end)