oj.uz

Submission #34201

# Submission time Handle Problem Language Result Execution time Memory
34201 2017-11-08T11:40:59 Z leejseo Jakarta Skyscrapers (APIO15_skyscraper) Python 2
0 / 100
 20 ms 3 KB 
#-*- 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())

def BFS(B, P, N):
    visited = [ [maxint]*N 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3 KB Output is correct
2 Runtime error 16 ms 3 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3 KB Output is correct
2 Runtime error 16 ms 3 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3 KB Output is correct
2 Runtime error 20 ms 3 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3 KB Output is correct
2 Runtime error 16 ms 3 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3 KB Output is correct
2 Runtime error 17 ms 3 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -