結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
![]() |
提出日時 | 2021-07-16 21:58:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,645 ms / 3,500 ms |
コード長 | 1,384 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 180,540 KB |
最終ジャッジ日時 | 2024-07-06 09:09:01 |
合計ジャッジ時間 | 32,791 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
mod = 1000000007 eps = 10**-9 L = 2*10**5 def main(): import sys from collections import deque input = sys.stdin.buffer.readline N, M, K = map(int, input().split()) ABC = [] adj = [[] for _ in range(N+1)] C01 = {} for _ in range(M): a, b, c = map(int, input().split()) ABC.append((a, b, c)) adj[a].append(b) adj[b].append(a) C01[a * (N + 1) + b] = 0 C01[b * (N + 1) + a] = 0 ok = L+1 ng = -1 mid = (ok + ng) // 2 while ok - ng > 1: for a, b, c in ABC: if c > mid: C01[a * (N + 1) + b] = 1 C01[b * (N + 1) + a] = 1 else: C01[a * (N + 1) + b] = 0 C01[b * (N + 1) + a] = 0 que = deque() que.append((1, 0)) seen = [-1] * (N+1) while que: v, d = que.popleft() if seen[v] != -1: continue seen[v] = d for u in adj[v]: c = C01[u * (N+1) + v] if seen[u] == -1: if c: que.append((u, d+1)) else: que.appendleft((u, d)) if seen[N] < K: ok = mid else: ng = mid mid = (ok + ng) // 2 print(ok) if __name__ == '__main__': main()