Submission #35725

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
35725	2017-11-29T03:24:05 Z	leejseo	Jakarta Skyscrapers (APIO15_skyscraper)	PyPy	57 / 100	1000 ms	29 KB

skyscraper

from heapq import *
from bisect import bisect_right
maxint = int(1E9)
 
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.0 / 10.0

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

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	5 KB	Output is correct
2	Correct	26 ms	5 KB	Output is correct
3	Correct	26 ms	5 KB	Output is correct
4	Correct	36 ms	5 KB	Output is correct
5	Correct	41 ms	5 KB	Output is correct
6	Correct	29 ms	5 KB	Output is correct
7	Correct	33 ms	5 KB	Output is correct
8	Correct	33 ms	5 KB	Output is correct
9	Correct	37 ms	5 KB	Output is correct
10	Correct	42 ms	6 KB	Output is correct
11	Correct	99 ms	9 KB	Output is correct
12	Correct	74 ms	9 KB	Output is correct
13	Correct	72 ms	9 KB	Output is correct
14	Correct	131 ms	10 KB	Output is correct
15	Correct	100 ms	10 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	10 KB	Output is correct
2	Correct	42 ms	10 KB	Output is correct
3	Correct	29 ms	10 KB	Output is correct
4	Correct	30 ms	10 KB	Output is correct
5	Correct	36 ms	10 KB	Output is correct
6	Correct	27 ms	10 KB	Output is correct
7	Correct	27 ms	10 KB	Output is correct
8	Correct	28 ms	10 KB	Output is correct
9	Correct	33 ms	10 KB	Output is correct
10	Correct	41 ms	10 KB	Output is correct
11	Correct	82 ms	10 KB	Output is correct
12	Correct	70 ms	10 KB	Output is correct
13	Correct	75 ms	10 KB	Output is correct
14	Correct	119 ms	10 KB	Output is correct
15	Correct	103 ms	10 KB	Output is correct
16	Correct	63 ms	10 KB	Output is correct
17	Correct	149 ms	12 KB	Output is correct
18	Correct	52 ms	12 KB	Output is correct
19	Correct	62 ms	12 KB	Output is correct
20	Correct	87 ms	12 KB	Output is correct
21	Correct	86 ms	12 KB	Output is correct
22	Correct	63 ms	12 KB	Output is correct
23	Correct	179 ms	12 KB	Output is correct
24	Correct	289 ms	15 KB	Output is correct
25	Correct	242 ms	15 KB	Output is correct
26	Correct	133 ms	15 KB	Output is correct
27	Correct	139 ms	15 KB	Output is correct
28	Correct	109 ms	15 KB	Output is correct
29	Correct	205 ms	15 KB	Output is correct
30	Correct	137 ms	15 KB	Output is correct
31	Correct	161 ms	15 KB	Output is correct
32	Correct	194 ms	15 KB	Output is correct
33	Correct	203 ms	16 KB	Output is correct
34	Correct	207 ms	18 KB	Output is correct

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	18 KB	Output is correct
2	Correct	26 ms	18 KB	Output is correct
3	Correct	27 ms	18 KB	Output is correct
4	Correct	28 ms	18 KB	Output is correct
5	Correct	27 ms	18 KB	Output is correct
6	Correct	27 ms	18 KB	Output is correct
7	Correct	32 ms	18 KB	Output is correct
8	Correct	36 ms	18 KB	Output is correct
9	Correct	28 ms	18 KB	Output is correct
10	Correct	38 ms	18 KB	Output is correct
11	Correct	86 ms	18 KB	Output is correct
12	Correct	74 ms	18 KB	Output is correct
13	Correct	84 ms	18 KB	Output is correct
14	Correct	138 ms	18 KB	Output is correct
15	Correct	101 ms	18 KB	Output is correct
16	Correct	87 ms	18 KB	Output is correct
17	Correct	197 ms	18 KB	Output is correct
18	Correct	62 ms	18 KB	Output is correct
19	Correct	47 ms	18 KB	Output is correct
20	Correct	101 ms	18 KB	Output is correct
21	Correct	74 ms	18 KB	Output is correct
22	Correct	56 ms	18 KB	Output is correct
23	Correct	184 ms	18 KB	Output is correct
24	Correct	246 ms	18 KB	Output is correct
25	Correct	245 ms	18 KB	Output is correct
26	Correct	167 ms	18 KB	Output is correct
27	Correct	174 ms	18 KB	Output is correct
28	Correct	106 ms	18 KB	Output is correct
29	Correct	213 ms	18 KB	Output is correct
30	Correct	146 ms	18 KB	Output is correct
31	Correct	186 ms	18 KB	Output is correct
32	Correct	194 ms	18 KB	Output is correct
33	Correct	256 ms	18 KB	Output is correct
34	Correct	230 ms	18 KB	Output is correct
35	Correct	251 ms	19 KB	Output is correct
36	Correct	189 ms	19 KB	Output is correct
37	Correct	253 ms	19 KB	Output is correct
38	Correct	261 ms	21 KB	Output is correct
39	Correct	257 ms	21 KB	Output is correct
40	Correct	312 ms	22 KB	Output is correct
41	Correct	341 ms	22 KB	Output is correct
42	Correct	232 ms	22 KB	Output is correct
43	Correct	206 ms	22 KB	Output is correct
44	Correct	114 ms	22 KB	Output is correct
45	Correct	280 ms	22 KB	Output is correct
46	Correct	284 ms	22 KB	Output is correct

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	22 KB	Output is correct
2	Correct	31 ms	22 KB	Output is correct
3	Correct	34 ms	22 KB	Output is correct
4	Correct	36 ms	22 KB	Output is correct
5	Correct	45 ms	22 KB	Output is correct
6	Correct	27 ms	22 KB	Output is correct
7	Correct	30 ms	22 KB	Output is correct
8	Correct	35 ms	22 KB	Output is correct
9	Correct	33 ms	22 KB	Output is correct
10	Correct	40 ms	22 KB	Output is correct
11	Correct	82 ms	22 KB	Output is correct
12	Correct	84 ms	22 KB	Output is correct
13	Correct	105 ms	22 KB	Output is correct
14	Correct	111 ms	22 KB	Output is correct
15	Correct	100 ms	22 KB	Output is correct
16	Correct	44 ms	22 KB	Output is correct
17	Correct	157 ms	22 KB	Output is correct
18	Correct	54 ms	22 KB	Output is correct
19	Correct	57 ms	22 KB	Output is correct
20	Correct	99 ms	22 KB	Output is correct
21	Correct	77 ms	22 KB	Output is correct
22	Correct	52 ms	22 KB	Output is correct
23	Correct	167 ms	22 KB	Output is correct
24	Correct	243 ms	22 KB	Output is correct
25	Correct	245 ms	22 KB	Output is correct
26	Correct	140 ms	22 KB	Output is correct
27	Correct	134 ms	22 KB	Output is correct
28	Correct	137 ms	22 KB	Output is correct
29	Correct	200 ms	22 KB	Output is correct
30	Correct	181 ms	22 KB	Output is correct
31	Correct	194 ms	22 KB	Output is correct
32	Correct	187 ms	22 KB	Output is correct
33	Correct	245 ms	22 KB	Output is correct
34	Correct	216 ms	22 KB	Output is correct
35	Correct	250 ms	22 KB	Output is correct
36	Correct	227 ms	22 KB	Output is correct
37	Correct	301 ms	22 KB	Output is correct
38	Correct	359 ms	22 KB	Output is correct
39	Correct	350 ms	22 KB	Output is correct
40	Correct	335 ms	22 KB	Output is correct
41	Correct	277 ms	22 KB	Output is correct
42	Correct	208 ms	22 KB	Output is correct
43	Correct	198 ms	22 KB	Output is correct
44	Correct	119 ms	22 KB	Output is correct
45	Correct	280 ms	22 KB	Output is correct
46	Correct	277 ms	22 KB	Output is correct
47	Correct	592 ms	24 KB	Output is correct
48	Correct	144 ms	24 KB	Output is correct
49	Correct	137 ms	24 KB	Output is correct
50	Correct	123 ms	24 KB	Output is correct
51	Correct	819 ms	29 KB	Output is correct
52	Correct	676 ms	29 KB	Output is correct
53	Correct	432 ms	29 KB	Output is correct
54	Correct	128 ms	29 KB	Output is correct
55	Correct	151 ms	29 KB	Output is correct
56	Execution timed out	1024 ms	29 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-

Submission #35725

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0