Submission #1170239

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1170239	2025-03-19 14:20:02	oasunmol	Jakarta Skyscrapers (APIO15_skyscraper)	Pypy 3	0 / 100	133 ms	48812 KiB

skyscraper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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