結果
問題 |
No.3291 K-step Navigation
|
ユーザー |
![]() |
提出日時 | 2025-10-06 21:43:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,409 ms / 3,000 ms |
コード長 | 2,834 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 82,640 KB |
実行使用メモリ | 99,880 KB |
最終ジャッジ日時 | 2025-10-06 21:43:17 |
合計ジャッジ時間 | 12,956 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 51 |
ソースコード
from collections import deque, defaultdict class UnionFind: def __init__(self,n): self.n = n self.parent_size = [-1]*n def leader(self,a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self,a,b): x, y = self.leader(a), self.leader(b) if x == y: return if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x return def same(self,a,b): return self.leader(a) == self.leader(b) def size(self,a): return abs(self.parent_size[self.leader(a)]) def groups(self): result = [[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return result def encode(n, d): return n*2+d def decode(n): return n//2, n%2 INF = 1<<60 N, M, K, S, T = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u, v = u-1, v-1 G[u].append(v) G[v].append(u) S, T = S-1, T-1 visited = [-1]*N visited[S] = 0 que = deque() que.append(S) while que: n = que.popleft() for v in G[n]: if visited[v] == -1: visited[v] = visited[n]+1 que.append(v) if K <= visited[T]: exit(print("Yes")) UF = UnionFind(N) for i in range(N): for v in G[i]: UF.merge(i, v) if visited[T] == -1 and UF.size(S) == UF.size(T) == 1 and K%2 == 0: print("No") elif UF.size(S) == 2 and UF.same(S, T) and K%2 == 0: if N == 2: print("No") else: MIN = INF groups = UF.groups() for i in range(N): if i == S or i == T: continue if UF.leader(i) != i: continue for j in groups[i]: visited = defaultdict(lambda: -1) visited[encode(j, 0)] = 0 que = deque() que.append(encode(j, 0)) flag = False while que: n, d = decode(que.popleft()) for v in G[n]: if visited[encode(v, d^1)] == -1: visited[encode(v, d^1)] = visited[encode(n, d)]+1 if v == j and d^1 == 1: MIN = min(MIN, visited[encode(v, d^1)]) flag = True break que.append(encode(v, d^1)) if flag: break if MIN+2+1 <= K: print("Yes") else: print("No") else: print("Yes")