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 = set()
count = 0
for i in range(m):
a,b = map(int, input().split())
if count == 1:
baka = a
if count == 0:
imposter = a
#sussy[a].append(b)
stuff.add((a,b))
count += 1
for i in stuff:
sus = i[0]
count = 0
while (sus+i[1])<n:
sus+=i[1]
count += 1
edges[i[0]].append((sus, count))
sus = i[0]
count = 0
while (sus-i[1])>=0:
sus -= i[1]
count += 1
edges[i[0]].append((sus, count))
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)[baka]
print(-1 if susz == inf else susz)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
18320 KB |
Output is correct |
2 |
Correct |
36 ms |
18308 KB |
Output is correct |
3 |
Correct |
38 ms |
18176 KB |
Output is correct |
4 |
Correct |
37 ms |
18244 KB |
Output is correct |
5 |
Correct |
37 ms |
18296 KB |
Output is correct |
6 |
Correct |
36 ms |
18264 KB |
Output is correct |
7 |
Correct |
38 ms |
18208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
18248 KB |
Output is correct |
2 |
Correct |
40 ms |
18256 KB |
Output is correct |
3 |
Correct |
46 ms |
18392 KB |
Output is correct |
4 |
Correct |
37 ms |
18260 KB |
Output is correct |
5 |
Correct |
39 ms |
18212 KB |
Output is correct |
6 |
Correct |
36 ms |
18192 KB |
Output is correct |
7 |
Correct |
37 ms |
18284 KB |
Output is correct |
8 |
Correct |
37 ms |
18260 KB |
Output is correct |
9 |
Correct |
41 ms |
18272 KB |
Output is correct |
10 |
Correct |
47 ms |
19028 KB |
Output is correct |
11 |
Correct |
82 ms |
20248 KB |
Output is correct |
12 |
Correct |
66 ms |
19208 KB |
Output is correct |
13 |
Correct |
55 ms |
19816 KB |
Output is correct |
14 |
Correct |
61 ms |
19860 KB |
Output is correct |
15 |
Correct |
61 ms |
20640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
18308 KB |
Output is correct |
2 |
Correct |
38 ms |
18292 KB |
Output is correct |
3 |
Correct |
40 ms |
18256 KB |
Output is correct |
4 |
Correct |
42 ms |
18256 KB |
Output is correct |
5 |
Correct |
46 ms |
18340 KB |
Output is correct |
6 |
Correct |
38 ms |
18248 KB |
Output is correct |
7 |
Correct |
40 ms |
18212 KB |
Output is correct |
8 |
Correct |
40 ms |
18308 KB |
Output is correct |
9 |
Correct |
40 ms |
18244 KB |
Output is correct |
10 |
Correct |
52 ms |
18964 KB |
Output is correct |
11 |
Correct |
65 ms |
20256 KB |
Output is correct |
12 |
Correct |
60 ms |
19212 KB |
Output is correct |
13 |
Correct |
70 ms |
19920 KB |
Output is correct |
14 |
Correct |
74 ms |
19964 KB |
Output is correct |
15 |
Correct |
63 ms |
20592 KB |
Output is correct |
16 |
Correct |
51 ms |
19200 KB |
Output is correct |
17 |
Correct |
119 ms |
24992 KB |
Output is correct |
18 |
Correct |
70 ms |
19620 KB |
Output is correct |
19 |
Correct |
56 ms |
19488 KB |
Output is correct |
20 |
Correct |
502 ms |
150224 KB |
Output is correct |
21 |
Correct |
63 ms |
19488 KB |
Output is correct |
22 |
Correct |
53 ms |
19980 KB |
Output is correct |
23 |
Correct |
108 ms |
22908 KB |
Output is correct |
24 |
Correct |
166 ms |
26324 KB |
Output is correct |
25 |
Correct |
194 ms |
26228 KB |
Output is correct |
26 |
Correct |
100 ms |
23692 KB |
Output is correct |
27 |
Correct |
93 ms |
23236 KB |
Output is correct |
28 |
Correct |
112 ms |
22644 KB |
Output is correct |
29 |
Correct |
139 ms |
26284 KB |
Output is correct |
30 |
Correct |
135 ms |
26492 KB |
Output is correct |
31 |
Correct |
140 ms |
26964 KB |
Output is correct |
32 |
Correct |
149 ms |
26252 KB |
Output is correct |
33 |
Correct |
156 ms |
30108 KB |
Output is correct |
34 |
Correct |
156 ms |
30192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
18320 KB |
Output is correct |
2 |
Correct |
37 ms |
18308 KB |
Output is correct |
3 |
Correct |
38 ms |
18248 KB |
Output is correct |
4 |
Correct |
40 ms |
18212 KB |
Output is correct |
5 |
Correct |
37 ms |
18280 KB |
Output is correct |
6 |
Correct |
44 ms |
18184 KB |
Output is correct |
7 |
Correct |
39 ms |
18332 KB |
Output is correct |
8 |
Correct |
39 ms |
18292 KB |
Output is correct |
9 |
Correct |
38 ms |
18268 KB |
Output is correct |
10 |
Correct |
46 ms |
18932 KB |
Output is correct |
11 |
Correct |
66 ms |
20228 KB |
Output is correct |
12 |
Correct |
50 ms |
19188 KB |
Output is correct |
13 |
Correct |
57 ms |
19868 KB |
Output is correct |
14 |
Correct |
62 ms |
19844 KB |
Output is correct |
15 |
Correct |
64 ms |
20556 KB |
Output is correct |
16 |
Correct |
51 ms |
19232 KB |
Output is correct |
17 |
Correct |
112 ms |
24896 KB |
Output is correct |
18 |
Correct |
55 ms |
19616 KB |
Output is correct |
19 |
Correct |
50 ms |
19484 KB |
Output is correct |
20 |
Correct |
492 ms |
150136 KB |
Output is correct |
21 |
Correct |
50 ms |
19476 KB |
Output is correct |
22 |
Correct |
55 ms |
20044 KB |
Output is correct |
23 |
Correct |
113 ms |
22852 KB |
Output is correct |
24 |
Correct |
163 ms |
26404 KB |
Output is correct |
25 |
Correct |
157 ms |
26512 KB |
Output is correct |
26 |
Correct |
119 ms |
23808 KB |
Output is correct |
27 |
Correct |
94 ms |
23320 KB |
Output is correct |
28 |
Correct |
87 ms |
22540 KB |
Output is correct |
29 |
Correct |
162 ms |
26348 KB |
Output is correct |
30 |
Correct |
144 ms |
26448 KB |
Output is correct |
31 |
Correct |
149 ms |
26868 KB |
Output is correct |
32 |
Correct |
133 ms |
26300 KB |
Output is correct |
33 |
Correct |
162 ms |
30128 KB |
Output is correct |
34 |
Correct |
222 ms |
30240 KB |
Output is correct |
35 |
Correct |
181 ms |
30400 KB |
Output is correct |
36 |
Correct |
140 ms |
26456 KB |
Output is correct |
37 |
Correct |
194 ms |
36000 KB |
Output is correct |
38 |
Correct |
210 ms |
35964 KB |
Output is correct |
39 |
Correct |
199 ms |
36056 KB |
Output is correct |
40 |
Correct |
196 ms |
35720 KB |
Output is correct |
41 |
Correct |
223 ms |
35408 KB |
Output is correct |
42 |
Correct |
108 ms |
24528 KB |
Output is correct |
43 |
Correct |
100 ms |
23192 KB |
Output is correct |
44 |
Correct |
511 ms |
150584 KB |
Output is correct |
45 |
Correct |
240 ms |
46064 KB |
Output is correct |
46 |
Correct |
230 ms |
46996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
18196 KB |
Output is correct |
2 |
Correct |
52 ms |
18176 KB |
Output is correct |
3 |
Correct |
50 ms |
18248 KB |
Output is correct |
4 |
Correct |
37 ms |
18324 KB |
Output is correct |
5 |
Correct |
37 ms |
18220 KB |
Output is correct |
6 |
Correct |
37 ms |
18208 KB |
Output is correct |
7 |
Correct |
37 ms |
18212 KB |
Output is correct |
8 |
Correct |
37 ms |
18204 KB |
Output is correct |
9 |
Correct |
38 ms |
18252 KB |
Output is correct |
10 |
Correct |
46 ms |
18976 KB |
Output is correct |
11 |
Correct |
63 ms |
20224 KB |
Output is correct |
12 |
Correct |
68 ms |
19148 KB |
Output is correct |
13 |
Correct |
65 ms |
19928 KB |
Output is correct |
14 |
Correct |
63 ms |
19924 KB |
Output is correct |
15 |
Correct |
61 ms |
20640 KB |
Output is correct |
16 |
Correct |
50 ms |
19180 KB |
Output is correct |
17 |
Correct |
109 ms |
24988 KB |
Output is correct |
18 |
Correct |
57 ms |
19720 KB |
Output is correct |
19 |
Correct |
53 ms |
19488 KB |
Output is correct |
20 |
Correct |
503 ms |
150244 KB |
Output is correct |
21 |
Correct |
50 ms |
19488 KB |
Output is correct |
22 |
Correct |
60 ms |
19948 KB |
Output is correct |
23 |
Correct |
124 ms |
22928 KB |
Output is correct |
24 |
Correct |
143 ms |
26396 KB |
Output is correct |
25 |
Correct |
154 ms |
26420 KB |
Output is correct |
26 |
Correct |
109 ms |
23780 KB |
Output is correct |
27 |
Correct |
108 ms |
23268 KB |
Output is correct |
28 |
Correct |
97 ms |
22560 KB |
Output is correct |
29 |
Correct |
134 ms |
26268 KB |
Output is correct |
30 |
Correct |
141 ms |
26412 KB |
Output is correct |
31 |
Correct |
147 ms |
26964 KB |
Output is correct |
32 |
Correct |
145 ms |
26328 KB |
Output is correct |
33 |
Correct |
161 ms |
30156 KB |
Output is correct |
34 |
Correct |
154 ms |
30264 KB |
Output is correct |
35 |
Correct |
173 ms |
30496 KB |
Output is correct |
36 |
Correct |
158 ms |
26520 KB |
Output is correct |
37 |
Correct |
193 ms |
36000 KB |
Output is correct |
38 |
Correct |
194 ms |
35988 KB |
Output is correct |
39 |
Correct |
204 ms |
35892 KB |
Output is correct |
40 |
Correct |
207 ms |
35908 KB |
Output is correct |
41 |
Correct |
204 ms |
35440 KB |
Output is correct |
42 |
Correct |
110 ms |
24472 KB |
Output is correct |
43 |
Correct |
103 ms |
23232 KB |
Output is correct |
44 |
Correct |
513 ms |
150596 KB |
Output is correct |
45 |
Correct |
240 ms |
45928 KB |
Output is correct |
46 |
Correct |
251 ms |
47076 KB |
Output is correct |
47 |
Correct |
395 ms |
65808 KB |
Output is correct |
48 |
Correct |
101 ms |
30936 KB |
Output is correct |
49 |
Correct |
87 ms |
28816 KB |
Output is correct |
50 |
Correct |
86 ms |
28576 KB |
Output is correct |
51 |
Correct |
477 ms |
49764 KB |
Output is correct |
52 |
Correct |
431 ms |
51560 KB |
Output is correct |
53 |
Correct |
229 ms |
35556 KB |
Output is correct |
54 |
Correct |
115 ms |
26404 KB |
Output is correct |
55 |
Correct |
108 ms |
28780 KB |
Output is correct |
56 |
Runtime error |
732 ms |
262148 KB |
Execution killed with signal 9 |
57 |
Halted |
0 ms |
0 KB |
- |