結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2025-04-24 12:27:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,255 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 82,708 KB |
実行使用メモリ | 225,240 KB |
最終ジャッジ日時 | 2025-04-24 12:28:20 |
合計ジャッジ時間 | 12,540 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 26 |
ソースコード
import sys from collections import deque def main(): input = sys.stdin.read().split() idx = 0 n = int(input[idx]); idx +=1 m = int(input[idx]); idx +=1 K = int(input[idx]); idx +=1 edges = [] max_c = 0 for _ in range(m): u = int(input[idx]); idx +=1 v = int(input[idx]); idx +=1 c = int(input[idx]); idx +=1 edges.append((u, v, c)) if c > max_c: max_c = c # Compute minimal path length using BFS adj_shortest = [[] for _ in range(n+1)] for u, v, c in edges: adj_shortest[u].append(v) adj_shortest[v].append(u) visited = [False]*(n+1) q = deque() q.append(1) visited[1] = True dist = [0]*(n+1) while q: u = q.popleft() if u == n: break for v in adj_shortest[u]: if not visited[v]: visited[v] = True dist[v] = dist[u] + 1 q.append(v) L = dist[n] if L <= K-1: print(0) return # Binary search left = 1 right = max_c answer = max_c unique_c = sorted(set(c for u, v, c in edges)) left = 0 right = len(unique_c) -1 def is_possible(x_val): adj = [[] for _ in range(n+1)] for u, v, c in edges: if c >= x_val: adj[u].append(v) adj[v].append(u) # Check connectivity visited = [False]*(n+1) q = deque([1]) visited[1] = True found = False while q: u = q.popleft() if u == n: found = True break for v in adj[u]: if not visited[v]: visited[v] = True q.append(v) if not found: return False # Find component containing 1 and N component = [] visited_comp = [False]*(n+1) q = deque([1]) visited_comp[1] = True while q: u = q.popleft() component.append(u) for v in adj[u]: if not visited_comp[v]: visited_comp[v] = True q.append(v) # Check if N is in component if not visited_comp[n]: return False # Check for cycle in the component parent = [0]*(n+1) has_cycle = False visited_cycle = [False]*(n+1) for u in component: if visited_cycle[u]: continue q = deque([u]) parent[u] = -1 visited_cycle[u] = True while q and not has_cycle: current = q.popleft() for v in adj[current]: if not visited_cycle[v]: visited_cycle[v] = True parent[v] = current q.append(v) else: if parent[current] != v: has_cycle = True break if has_cycle: break if has_cycle: return True # Compute longest path (BFS distance in tree) distance = [-1]*(n+1) q = deque([1]) distance[1] = 0 while q: u = q.popleft() if u == n: break for v in adj[u]: if distance[v] == -1: distance[v] = distance[u] + 1 q.append(v) return distance[n] >= K # Binary search on unique_c unique_c.sort() left = 0 right = len(unique_c) -1 answer = max_c while left <= right: mid = (left + right) // 2 x_val = unique_c[mid] if is_possible(x_val): answer = x_val right = mid -1 else: left = mid +1 # Check if answer is found in unique_c, else check between # If not found, there might be a value between unique_c elements # So we need to collect all possible c's and binary search accordingly # But since the problem requires the K-th largest, which must be one of the c's, we can proceed with unique_c print(answer) if __name__ == '__main__': main()