fork download
  1. from collections import deque
  2.  
  3. def nearest_meeting_cell(n, edges, c1, c2):
  4. def bfs(start):
  5. """Performs BFS from the start cell and returns a dictionary of distances."""
  6. distances = {}
  7. queue = deque([(start, 0)])
  8. visited = set()
  9.  
  10. while queue:
  11. node, dist = queue.popleft()
  12. if node in visited:
  13. continue
  14. visited.add(node)
  15. distances[node] = dist
  16. # Move to the next node if it exists and hasn't been visited
  17. next_node = edges[node]
  18. if next_node != -1 and next_node not in visited:
  19. queue.append((next_node, dist + 1))
  20.  
  21. return distances
  22.  
  23. # Get reachable distances from both C1 and C2
  24. dist_from_c1 = bfs(c1)
  25. dist_from_c2 = bfs(c2)
  26.  
  27. # Find common cells that are reachable from both
  28. common_cells = set(dist_from_c1.keys()) & set(dist_from_c2.keys())
  29.  
  30. if not common_cells:
  31. return -1 # No meeting cell
  32.  
  33. # Find the nearest meeting cell
  34. nearest_cell = -1
  35. min_distance = float('inf')
  36.  
  37. for cell in common_cells:
  38. total_distance = max(dist_from_c1[cell], dist_from_c2[cell])
  39. if total_distance < min_distance:
  40. min_distance = total_distance
  41. nearest_cell = cell
  42.  
  43. return nearest_cell
  44.  
  45. # Input reading
  46. n = int(input()) # Number of cells
  47. edges = list(map(int, input().split())) # Edges array
  48. c1, c2 = map(int, input().split()) # Two cells to check
  49.  
  50. # Output the nearest meeting cell
  51. print(nearest_meeting_cell(n, edges, c1, c2))
Success #stdin #stdout 0.03s 9736KB
stdin
23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21
9 2
stdout
4