oj.uz

Submission #34208

# Submission time Handle Problem Language Result Execution time Memory
34208 2017-11-08T12:00:55 Z leejseo Jakarta Skyscrapers (APIO15_skyscraper) Python 2
10 / 100
 39 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())

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2 KB Output is correct
2 Correct 16 ms 3 KB Output is correct
3 Correct 17 ms 3 KB Output is correct
4 Correct 14 ms 3 KB Output is correct
5 Correct 13 ms 3 KB Output is correct
6 Correct 14 ms 3 KB Output is correct
7 Correct 14 ms 3 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3 KB Output is correct
2 Correct 14 ms 3 KB Output is correct
3 Correct 14 ms 3 KB Output is correct
4 Correct 14 ms 3 KB Output is correct
5 Correct 16 ms 3 KB Output is correct
6 Correct 14 ms 3 KB Output is correct
7 Correct 23 ms 3 KB Output is correct
8 Correct 17 ms 3 KB Output is correct
9 Correct 18 ms 3 KB Output is correct
10 Correct 19 ms 3 KB Output is correct
11 Incorrect 38 ms 3 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3 KB Output is correct
2 Correct 14 ms 3 KB Output is correct
3 Correct 14 ms 3 KB Output is correct
4 Correct 15 ms 3 KB Output is correct
5 Correct 18 ms 3 KB Output is correct
6 Correct 16 ms 3 KB Output is correct
7 Correct 14 ms 3 KB Output is correct
8 Correct 17 ms 3 KB Output is correct
9 Correct 14 ms 3 KB Output is correct
10 Correct 22 ms 3 KB Output is correct
11 Incorrect 39 ms 3 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3 KB Output is correct
2 Correct 17 ms 3 KB Output is correct
3 Correct 17 ms 3 KB Output is correct
4 Correct 14 ms 3 KB Output is correct
5 Correct 16 ms 3 KB Output is correct
6 Correct 18 ms 3 KB Output is correct
7 Correct 17 ms 3 KB Output is correct
8 Correct 18 ms 3 KB Output is correct
9 Correct 17 ms 3 KB Output is correct
10 Correct 20 ms 3 KB Output is correct
11 Incorrect 39 ms 3 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3 KB Output is correct
2 Correct 14 ms 3 KB Output is correct
3 Correct 14 ms 3 KB Output is correct
4 Correct 14 ms 3 KB Output is correct
5 Correct 17 ms 3 KB Output is correct
6 Correct 17 ms 3 KB Output is correct
7 Correct 15 ms 3 KB Output is correct
8 Correct 14 ms 3 KB Output is correct
9 Correct 17 ms 3 KB Output is correct
10 Correct 20 ms 3 KB Output is correct
11 Incorrect 33 ms 3 KB Output isn't correct
12 Halted 0 ms 0 KB -