Submission #35685

#	Time	Username	Problem	Language	Result	Execution time	Memory
35685		leejseo	Jakarta Skyscrapers (APIO15_skyscraper)	Pypy 2	57 / 100	1054 ms	98 KiB

skyscraper

from heapq import *
from bisect import bisect_right
maxint = int(2E9)

class Node(object):
    def __init__(self, u, dist):
        self.u = u
        self.dist = dist
    
    def __cmp__(self, other):
        return cmp(self.dist, other.dist)

def binary_search(L, val):
    if not L : return False
    s = bisect_right(L, val)
    return L[s-1] == val

def dijkstra(start):
    global N, M, V, B, P
    dist = [maxint for i in range(N)]    
    start = B[0]
    dist[start] = 0
    Q = []
    heappush(Q, Node(start, 0))
    while Q :
        node = heappop(Q)
        u, dist_u = node.u, node.dist
        if dist_u > dist[u] : continue
        for power in V[u]:
            to = u+power
            cost = dist_u + 1
            while to < N :
                if dist[to] > cost :
                    dist[to] = cost
                    heappush(Q, Node(to, cost))
                    if binary_search(V[to], power):
                        break
                to += power
                cost += 1
            to = u-power
            cost = dist_u + 1
            while to >= 0 : 
                if dist[to] > cost :
                    dist[to] = cost
                    heappush(Q, Node(to, cost))
                    if binary_search(V[to], power):
                        break
                to -= power
                cost += 1
    return dist

def main():
    global N, M, V, B, P   
    N, M = map(int, raw_input().split())
    V = [ [] for i in range(N) ]
    B = [None for i in range(M)]
    P = [None for i in range(M)]
    for i in range(M):
        B[i], P[i] = map(int, raw_input().split())
        V[B[i]].append(P[i])
        
    for i in range(N):
        V[i] = list(set(V[i]))
        V[i].sort()
    start = B[0]
    dist = dijkstra(start)
    ans = dist[B[1]]
    if ans == maxint: print -1
    else: print ans
    return
main()

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