oj.uz

Submission #1052856

# Submission time Handle Problem Language Result Execution time Memory
1052856 2024-08-11T04:54:26 Z amongus_pvp Jakarta Skyscrapers (APIO15_skyscraper) Python 3
0 / 100
 12 ms 3320 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -