oj.uz

Submission #34225

# Submission time Handle Problem Language Result Execution time Memory
34225 2017-11-08T13:07:58 Z leejseo Jakarta Skyscrapers (APIO15_skyscraper) Python 2
10 / 100
 1000 ms 53 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 13 ms 2 KB Output is correct
2 Correct 13 ms 2 KB Output is correct
3 Correct 13 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 17 ms 3 KB Output is correct
7 Correct 13 ms 3 KB Output is correct

Subtask #2
0 / 12.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 15 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 15 ms 3 KB Output is correct
10 Correct 83 ms 6 KB Output is correct
11 Execution timed out 1065 ms 52 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 52 KB Output is correct
2 Correct 16 ms 52 KB Output is correct
3 Correct 17 ms 52 KB Output is correct
4 Correct 13 ms 52 KB Output is correct
5 Correct 14 ms 52 KB Output is correct
6 Correct 13 ms 52 KB Output is correct
7 Correct 13 ms 52 KB Output is correct
8 Correct 14 ms 52 KB Output is correct
9 Correct 15 ms 52 KB Output is correct
10 Correct 95 ms 52 KB Output is correct
11 Execution timed out 1071 ms 52 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 52 KB Output is correct
2 Correct 17 ms 52 KB Output is correct
3 Correct 13 ms 52 KB Output is correct
4 Correct 13 ms 52 KB Output is correct
5 Correct 13 ms 52 KB Output is correct
6 Correct 13 ms 52 KB Output is correct
7 Correct 13 ms 52 KB Output is correct
8 Correct 14 ms 52 KB Output is correct
9 Correct 15 ms 52 KB Output is correct
10 Correct 84 ms 52 KB Output is correct
11 Execution timed out 1064 ms 52 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 52 KB Output is correct
2 Correct 13 ms 52 KB Output is correct
3 Correct 13 ms 52 KB Output is correct
4 Correct 15 ms 52 KB Output is correct
5 Correct 13 ms 52 KB Output is correct
6 Correct 16 ms 52 KB Output is correct
7 Correct 19 ms 52 KB Output is correct
8 Correct 17 ms 52 KB Output is correct
9 Correct 15 ms 52 KB Output is correct
10 Correct 83 ms 52 KB Output is correct
11 Execution timed out 1072 ms 53 KB Time limit exceeded
12 Halted 0 ms 0 KB -