Submission #1052856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052856		amongus_pvp	Jakarta Skyscrapers (APIO15_skyscraper)	Cpython 3	0 / 100	12 ms	3320 KiB

skyscraper

from collections import deque, defaultdict

def min_jumps_to_pass_news(N, M, doges):
    # Graph to hold connections (skyscrapers reachable by jumps)
    graph = defaultdict(list)
    for i, (b, p) in enumerate(doges):
        graph[b].append((b + p, i))
        graph[b].append((b - p, i))
    
    # Initialize BFS
    queue = deque()
    visited = [False] * N
    min_jumps = [float('inf')] * N
    doge_locations = [b for b, _ in doges]
    
    # Start with doge 0
    queue.append((doge_locations[0], 0))  # (current_skyscraper, jumps)
    visited[doge_locations[0]] = True
    min_jumps[doge_locations[0]] = 0
    
    while queue:
        current, jumps = queue.popleft()
        
        # Check if we reached skyscraper with doge 1
        if visited[1]:
            return min_jumps[1]
        
        for next_skyscraper, doge_index in graph[current]:
            if 0 <= next_skyscraper < N and not visited[next_skyscraper]:
                visited[next_skyscraper] = True
                min_jumps[next_skyscraper] = jumps + 1
                queue.append((next_skyscraper, jumps + 1))
                
                # Pass the news to other doges in the same skyscraper
                for i in range(M):
                    if doge_locations[i] == next_skyscraper:
                        queue.append((next_skyscraper, jumps + 1))
                        visited[next_skyscraper] = True
    
    return -1 if min_jumps[1] == float('inf') else min_jumps[1]

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43