Submission #1170239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170239		oasunmol	Jakarta Skyscrapers (APIO15_skyscraper)	Pypy 3	0 / 100	133 ms	48812 KiB

skyscraper

import heapq
from collections import defaultdict
import sys

# Constants
BUC = 175  # Jump threshold
INF = float('inf')

def min_jumps_to_doge1(N, M, doges):
    # Step 1: Construct adjacency list (doges per skyscraper)
    skyscraper_doges = defaultdict(list)
    for i, (B, P) in enumerate(doges):
        skyscraper_doges[B].append((i, P))  # Doge index and power

    # Step 2: Dijkstra Initialization
    dist = {}  # Dictionary to store the minimum jumps needed
    pq = []  # Min heap for Dijkstra's algorithm
    
    # Push starting position (Doge 0) into priority queue
    heapq.heappush(pq, (0, doges[0][0], 0))  # (jumps, position, power)
    dist[(doges[0][0], 0)] = 0  # Distance to Doge 0's initial position is 0

    while pq:
        jumps, pos, power = heapq.heappop(pq)

        # If we reach Doge 1, return the minimum jumps
        if pos == doges[1][0]:
            return jumps

        # Step 3: Passing news to other doges at the same skyscraper
        for _, new_power in skyscraper_doges[pos]:
            if (pos, new_power) not in dist or dist[(pos, new_power)] > jumps:
                dist[(pos, new_power)] = jumps
                heapq.heappush(pq, (jumps, pos, new_power))

        # Step 4: Moving using jumps
        if power > 0:  # If doge has jumping power
            for new_pos in (pos + power, pos - power):
                if 0 <= new_pos < N:  # Ensure within bounds
                    if (new_pos, 0) not in dist or dist[(new_pos, 0)] > jumps + 1:
                        dist[(new_pos, 0)] = jumps + 1
                        heapq.heappush(pq, (jumps + 1, new_pos, 0))

    return -1  # If we never reach Doge 1

# Read input
N, M = map(int, sys.stdin.readline().split())
doges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]

# Output the result
print(min_jumps_to_doge1(N, M, doges))

Compilation message (stdout)

Compiling 'skyscraper.py'...

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

=======

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