oj.uz

Submission #34226

# Submission time Handle Problem Language Result Execution time Memory
34226 2017-11-08T13:08:58 Z leejseo Jakarta Skyscrapers (APIO15_skyscraper) PyPy
10 / 100
 1000 ms 256 KB 
from heapq import *
MAX_INT = int(2E9)

class Edge(object):
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

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 dijkstra(V, start, adj_list):
    Q = []
    dist = [MAX_INT for i in range(V)]
    dist[start] = 0
    heappush(Q, Node(start, 0))
    while Q:
        u = Q[0].u
        dist_u = Q[0].dist
        heappop(Q)
        if dist[u] < dist_u :
            continue
        for i in range(len(adj_list[u])):
            v = adj_list[u][i].to
            dist_v = dist_u + adj_list[u][i].weight
            
            if dist_v < dist[v]:
                dist[v] = dist_v
                heappush(Q, Node(v, dist_v))
    return dist

N, M = map(int, raw_input().split())
doge = [None]*M
for i in range(M):
    doge[i] = map(int, raw_input().split())

adj_list = [ [] for i in range(M) ]

for i in range(M):
    for j in range(M):
        if i != j and ((doge[i][0] - doge[j][0])%doge[i][1] == 0 ):
            adj_list[i].append(Edge(j, abs(doge[i][0] - doge[j][0])/doge[i][1]))

ans = dijkstra(M, 0, adj_list)

if ans[1] == MAX_INT:
    print -1
else:
    print ans[1]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 36 KB Output is correct
2 Correct 32 ms 36 KB Output is correct
3 Correct 29 ms 36 KB Output is correct
4 Correct 25 ms 36 KB Output is correct
5 Correct 25 ms 36 KB Output is correct
6 Correct 28 ms 36 KB Output is correct
7 Correct 31 ms 36 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 36 KB Output is correct
2 Correct 32 ms 36 KB Output is correct
3 Correct 26 ms 36 KB Output is correct
4 Correct 26 ms 36 KB Output is correct
5 Correct 26 ms 36 KB Output is correct
6 Correct 23 ms 36 KB Output is correct
7 Correct 25 ms 36 KB Output is correct
8 Correct 26 ms 36 KB Output is correct
9 Correct 52 ms 39 KB Output is correct
10 Correct 116 ms 45 KB Output is correct
11 Correct 374 ms 66 KB Output is correct
12 Execution timed out 1047 ms 256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 256 KB Output is correct
2 Correct 25 ms 256 KB Output is correct
3 Correct 24 ms 256 KB Output is correct
4 Correct 27 ms 256 KB Output is correct
5 Correct 26 ms 256 KB Output is correct
6 Correct 25 ms 256 KB Output is correct
7 Correct 32 ms 256 KB Output is correct
8 Correct 25 ms 256 KB Output is correct
9 Correct 43 ms 256 KB Output is correct
10 Correct 115 ms 256 KB Output is correct
11 Correct 377 ms 256 KB Output is correct
12 Execution timed out 1053 ms 256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 256 KB Output is correct
2 Correct 31 ms 256 KB Output is correct
3 Correct 27 ms 256 KB Output is correct
4 Correct 28 ms 256 KB Output is correct
5 Correct 26 ms 256 KB Output is correct
6 Correct 32 ms 256 KB Output is correct
7 Correct 26 ms 256 KB Output is correct
8 Correct 27 ms 256 KB Output is correct
9 Correct 36 ms 256 KB Output is correct
10 Correct 115 ms 256 KB Output is correct
11 Correct 379 ms 256 KB Output is correct
12 Execution timed out 1055 ms 256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 256 KB Output is correct
2 Correct 31 ms 256 KB Output is correct
3 Correct 33 ms 256 KB Output is correct
4 Correct 43 ms 256 KB Output is correct
5 Correct 30 ms 256 KB Output is correct
6 Correct 29 ms 256 KB Output is correct
7 Correct 29 ms 256 KB Output is correct
8 Correct 31 ms 256 KB Output is correct
9 Correct 41 ms 256 KB Output is correct
10 Correct 124 ms 256 KB Output is correct
11 Correct 435 ms 256 KB Output is correct
12 Execution timed out 1065 ms 256 KB Time limit exceeded
13 Halted 0 ms 0 KB -