Submission #1241072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241072		woe	Circle Passing (EGOI24_circlepassing)	Pypy 3	0 / 100	713 ms	1114112 KiB

Main

from collections import deque

def bfs(start, end, adj_list, n):
    visited = [-1] * (n + 1)
    queue = deque([start])
    visited[start] = 0
    
    while queue:
        current = queue.popleft()
        for neighbor in adj_list[current]:
            if visited[neighbor] == -1:
                visited[neighbor] = visited[current] + 1
                if neighbor == end:
                    return visited[neighbor]
                queue.append(neighbor)
    return -1

def solve_circle_passing(n, m, games, best_friend_pairs):
    adj_list = [[] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        adj_list[i].append(i % n + 1)
        adj_list[i % n + 1].append(i)
    
    for a, b in best_friend_pairs:
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    results = []
    for start, end in games:
        results.append(bfs(start, end, adj_list, n))
    
    return results

n, m, k = map(int, input().split())
best_friend_pairs = [tuple(map(int, input().split())) for _ in range(m)]
games = [tuple(map(int, input().split())) for _ in range(k)]

results = solve_circle_passing(n, m, games, best_friend_pairs)
for result in results:
    print(result)

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 44%)

=======

• Subtask 1: 0 / 14
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27