Submission #34208

#	Time	Username	Problem	Language	Result	Execution time	Memory
34208		leejseo	Jakarta Skyscrapers (APIO15_skyscraper)	Cpython 2	10 / 100	39 ms	3 KiB

skyscraper

#-*- coding: utf-8 -*-
maxint = int(2E9)
from collections import deque
N, M = map(int, raw_input().split())
B = [None]*M
P = [None]*M
for i in range(M):
    B[i], P[i] = map(int, raw_input().split())

K = max(P)+1

def BFS(B, P, N):
    visited = [ [maxint]*K for i in range(N) ]
    initial_pos = [[] for i in range(N) ]
    for i in range(len(B)):
        initial_pos[B[i]].append(P[i])
    #### NOTE : visited[i][j] = pos : i, power : j ####
    spos, spower = B[0], P[0]
    gpos, gpower = B[1], P[1]
    visited[spos][spower] = 0
    Q = deque([(spos, spower)])
    while Q:
        #print Q
        pos, power = Q.popleft()
        val = visited[pos][power]
        if pos - power > 0 :
            if visited[pos-power][power] == maxint:
                Q.append((pos-power, power))
                visited[pos-power][power] = val + 1
            if initial_pos[pos-power]:
                for n_power in initial_pos[pos-power]:
                    if n_power == power : continue
                    if visited[pos-power][n_power] == maxint:
                        visited[pos-power][n_power] = val + 1
                        Q.append((pos-power, n_power))
        if pos + power < N :
            if visited[pos+power][power] == maxint:
                Q.append((pos+power, power))
                visited[pos+power][power] = val + 1
            if initial_pos[pos+power]:
                for n_power in initial_pos[pos+power]:
                    if n_power == power : continue
                    if visited[pos+power][n_power] == maxint:
                        visited[pos+power][n_power] = val+1
                        Q.append((pos+power, n_power))
    #for i in visited: print i
    ans = min(visited[gpos])
    if ans == maxint: return -1
    return ans
print BFS(B, P, N)

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