Submission #1239839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239839		woe	Circle Passing (EGOI24_circlepassing)	Pypy 3	0 / 100	134 ms	48784 KiB

Main

from collections import deque

def solve(N, M, Q, friends, queries):
    G = [[] for _ in range(2*N)]
    for i in range(2*N):
        G[i].append((i + 1) % (2*N))
        G[i].append((i - 1) % (2*N))
    for k in friends:
        G[k].append(k + N)
        G[k + N].append(k)

    def bfs(x, y):
        dist = [-1] * (2*N)
        q = deque([x])
        dist[x] = 0
        while q:
            v = q.popleft()
            if v == y:
                return dist[v]
            for u in G[v]:
                if dist[u] == -1:
                    dist[u] = dist[v] + 1
                    q.append(u)
        return -1

    return [bfs(x, y) for x, y in queries]

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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