Submission #482545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
482545	2021-10-25T14:07:03 Z	beaconmc	Jakarta Skyscrapers (APIO15_skyscraper)	PyPy 3	10 / 100	71 ms	20184 KB

skyscraper

import io, os
from math import *
from heapq import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, m = map(int, input().split())

edges = [[] for i in range(n)]
sussy = [[] for i in range(n)]
stuff = []
count = 0
for i in range(m):
    a,b = map(int, input().split())
    if count == 1:
        sus = a
    if count == 0:
        imposter = a
    sussy[a].append(b)
    count += 1

for i in range(n):
    for j in range(i+1,n):
        for k in sussy[i]:
            if i%k == j%k:
                edges[i].append((j, abs(i-j)//k))
                break
            
        for k in sussy[j]:
            if i%k == j%k:
                edges[j].append((i, abs(i-j)//k))
                break
            
def djk(src):
    dist = [inf for i in range(n)]
    dist[src] = 0
    q = []
    heapify(q)
    heappush(q, (dist[src], src))
    while len(q):
        node = heappop(q)
        if dist[node[1]] != node[0]:
            continue
        
        for i in edges[node[1]]:
            if dist[i[0]] > node[0] + i[1]:
                dist[i[0]] = node[0] + i[1]
                heappush(q, (node[0]+i[1], i[0]))
    return dist
susz = djk(imposter)[sus]
print(-1 if susz == inf else susz)

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	18272 KB	Output is correct
2	Correct	39 ms	18208 KB	Output is correct
3	Correct	41 ms	18316 KB	Output is correct
4	Correct	37 ms	18304 KB	Output is correct
5	Correct	35 ms	18288 KB	Output is correct
6	Correct	36 ms	18192 KB	Output is correct
7	Correct	42 ms	18212 KB	Output is correct

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	18212 KB	Output is correct
2	Correct	43 ms	18436 KB	Output is correct
3	Correct	48 ms	18204 KB	Output is correct
4	Correct	37 ms	18212 KB	Output is correct
5	Correct	36 ms	18232 KB	Output is correct
6	Correct	36 ms	18272 KB	Output is correct
7	Correct	35 ms	18272 KB	Output is correct
8	Correct	36 ms	18232 KB	Output is correct
9	Correct	45 ms	19324 KB	Output is correct
10	Correct	56 ms	19484 KB	Output is correct
11	Correct	70 ms	20184 KB	Output is correct
12	Correct	51 ms	19540 KB	Output is correct
13	Correct	55 ms	19964 KB	Output is correct
14	Correct	63 ms	19872 KB	Output is correct
15	Incorrect	66 ms	20012 KB	Output isn't correct

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	18252 KB	Output is correct
2	Correct	46 ms	18308 KB	Output is correct
3	Correct	42 ms	18224 KB	Output is correct
4	Correct	38 ms	18260 KB	Output is correct
5	Correct	36 ms	18244 KB	Output is correct
6	Correct	37 ms	18212 KB	Output is correct
7	Correct	37 ms	18308 KB	Output is correct
8	Correct	42 ms	18260 KB	Output is correct
9	Correct	46 ms	19140 KB	Output is correct
10	Correct	62 ms	19484 KB	Output is correct
11	Correct	62 ms	20036 KB	Output is correct
12	Correct	53 ms	19648 KB	Output is correct
13	Correct	68 ms	19968 KB	Output is correct
14	Correct	65 ms	19872 KB	Output is correct
15	Incorrect	68 ms	20136 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	18256 KB	Output is correct
2	Correct	36 ms	18296 KB	Output is correct
3	Correct	35 ms	18212 KB	Output is correct
4	Correct	46 ms	18292 KB	Output is correct
5	Correct	39 ms	18212 KB	Output is correct
6	Correct	37 ms	18268 KB	Output is correct
7	Correct	38 ms	18216 KB	Output is correct
8	Correct	38 ms	18232 KB	Output is correct
9	Correct	46 ms	19224 KB	Output is correct
10	Correct	60 ms	19424 KB	Output is correct
11	Correct	67 ms	20116 KB	Output is correct
12	Correct	57 ms	19616 KB	Output is correct
13	Correct	57 ms	19920 KB	Output is correct
14	Correct	71 ms	19872 KB	Output is correct
15	Incorrect	66 ms	20016 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	18224 KB	Output is correct
2	Correct	43 ms	18240 KB	Output is correct
3	Correct	45 ms	18304 KB	Output is correct
4	Correct	36 ms	18252 KB	Output is correct
5	Correct	39 ms	18308 KB	Output is correct
6	Correct	35 ms	18248 KB	Output is correct
7	Correct	39 ms	18320 KB	Output is correct
8	Correct	39 ms	18304 KB	Output is correct
9	Correct	48 ms	19220 KB	Output is correct
10	Correct	55 ms	19488 KB	Output is correct
11	Correct	62 ms	20032 KB	Output is correct
12	Correct	55 ms	19640 KB	Output is correct
13	Correct	59 ms	19852 KB	Output is correct
14	Correct	67 ms	19820 KB	Output is correct
15	Incorrect	68 ms	19996 KB	Output isn't correct
16	Halted	0 ms	0 KB	-