// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123
const int N = 30007;
const int M = 8e6 + 7;
const int INF = 1e9 + 7;
pi a[N];
int d[M];
int m, n, s, f;
vector < pi > g[M];
main(){ // If you don't know what to do, check the text box at the bottom
cin >> m >> n;
for (int i = 1; i <= n; i++){
scanf("%d%d", &a[i].fr, &a[i].sc);
a[i].fr++;
}
s = a[1].fr, f = a[2].fr;
sort(a + 1, a + n + 1);
int k = unique(a + 1, a + n + 1) - a;
for (int i = 1; i < k; i++){
if (a[i].sc <= 250)
g[a[i].fr].pb(mk(m + (a[i].fr - 1) * 250 + a[i].sc, 0));
else {
int pos = a[i].fr, pw = a[i].sc, c = 0;
while (pos + pw <= m){
pos += pw; c++;
g[a[i].fr].pb(mk(pos, c));
}
pos = a[i].fr, c = 0;
while (pos - pw > 0){
pos -= pw; c++;
g[a[i].fr].pb(mk(pos, c));
}
}
}
for (int i = 1; i <= m; i++){
for (int j = 1; j <= 250; j++){
if (i + j <= m){
g[m + (i - 1) * 250 + j].pb(mk(m + (i + j - 1) * 250 + j, 1));
g[m + (i - 1) * 250 + j].pb(mk(i + j, 1));
}
if (i - j > 0){
g[m + (i - 1) * 250 + j].pb(mk(m + (i - j - 1) * 250 + j, 1));
g[m + (i - 1) * 250 + j].pb(mk(i - j, 1));
}
}
}
priority_queue < pi > pq;
pq.push(mk(0, s));
memset(d, 0x3f3f3f3f, sizeof(d));
d[s] = 0;
while (!pq.empty()){
int w = -pq.top().fr, v = pq.top().sc;
pq.pop();
if (d[v] < w)
continue;
for (pi to : g[v]){
if (d[to.fr] > d[v] + to.sc){
d[to.fr] = d[v] + to.sc;
pq.push(mk(-d[to.fr], to.fr));
}
}
}
if (d[f] != d[0])
printf("%d", d[f]);
else
puts("-1");
}
/*
Totally not inspired by BenQ's template
Things you should do:
1. Look for stupid typos in code e.g 1 instead of -1 etc
2. Check if there is no infinite loops
3. "Measure twice, cut once"
4. Stay focused
*/
Compilation message
skyscraper.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){ // If you don't know what to do, check the text box at the bottom
^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i].fr, &a[i].sc);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
228 ms |
219640 KB |
Output is correct |
2 |
Correct |
229 ms |
219516 KB |
Output is correct |
3 |
Correct |
226 ms |
219596 KB |
Output is correct |
4 |
Correct |
228 ms |
219512 KB |
Output is correct |
5 |
Correct |
251 ms |
219512 KB |
Output is correct |
6 |
Correct |
224 ms |
219444 KB |
Output is correct |
7 |
Correct |
230 ms |
219432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
219480 KB |
Output is correct |
2 |
Correct |
229 ms |
219724 KB |
Output is correct |
3 |
Correct |
231 ms |
219816 KB |
Output is correct |
4 |
Correct |
227 ms |
219584 KB |
Output is correct |
5 |
Correct |
228 ms |
219532 KB |
Output is correct |
6 |
Correct |
231 ms |
219596 KB |
Output is correct |
7 |
Correct |
224 ms |
219524 KB |
Output is correct |
8 |
Correct |
233 ms |
219704 KB |
Output is correct |
9 |
Correct |
235 ms |
219640 KB |
Output is correct |
10 |
Correct |
235 ms |
219824 KB |
Output is correct |
11 |
Correct |
239 ms |
219916 KB |
Output is correct |
12 |
Correct |
236 ms |
219908 KB |
Output is correct |
13 |
Correct |
238 ms |
219768 KB |
Output is correct |
14 |
Correct |
234 ms |
219764 KB |
Output is correct |
15 |
Correct |
247 ms |
219896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
219512 KB |
Output is correct |
2 |
Correct |
241 ms |
219512 KB |
Output is correct |
3 |
Correct |
230 ms |
219512 KB |
Output is correct |
4 |
Correct |
235 ms |
219512 KB |
Output is correct |
5 |
Correct |
233 ms |
219512 KB |
Output is correct |
6 |
Correct |
236 ms |
219600 KB |
Output is correct |
7 |
Correct |
233 ms |
219636 KB |
Output is correct |
8 |
Correct |
234 ms |
219512 KB |
Output is correct |
9 |
Correct |
235 ms |
219512 KB |
Output is correct |
10 |
Correct |
231 ms |
219896 KB |
Output is correct |
11 |
Correct |
235 ms |
219768 KB |
Output is correct |
12 |
Correct |
238 ms |
219868 KB |
Output is correct |
13 |
Correct |
237 ms |
220008 KB |
Output is correct |
14 |
Correct |
235 ms |
219912 KB |
Output is correct |
15 |
Correct |
234 ms |
219904 KB |
Output is correct |
16 |
Correct |
235 ms |
220672 KB |
Output is correct |
17 |
Correct |
267 ms |
227408 KB |
Output is correct |
18 |
Correct |
306 ms |
239096 KB |
Output is correct |
19 |
Correct |
319 ms |
242092 KB |
Output is correct |
20 |
Correct |
334 ms |
242164 KB |
Output is correct |
21 |
Correct |
261 ms |
223196 KB |
Output is correct |
22 |
Correct |
307 ms |
239480 KB |
Output is correct |
23 |
Correct |
302 ms |
237276 KB |
Output is correct |
24 |
Correct |
319 ms |
240940 KB |
Output is correct |
25 |
Correct |
338 ms |
242040 KB |
Output is correct |
26 |
Correct |
322 ms |
242060 KB |
Output is correct |
27 |
Correct |
321 ms |
242004 KB |
Output is correct |
28 |
Correct |
326 ms |
242304 KB |
Output is correct |
29 |
Correct |
330 ms |
242016 KB |
Output is correct |
30 |
Correct |
322 ms |
242068 KB |
Output is correct |
31 |
Correct |
328 ms |
242016 KB |
Output is correct |
32 |
Correct |
325 ms |
242212 KB |
Output is correct |
33 |
Correct |
368 ms |
242180 KB |
Output is correct |
34 |
Correct |
356 ms |
242296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
234 ms |
219460 KB |
Output is correct |
2 |
Correct |
229 ms |
219512 KB |
Output is correct |
3 |
Correct |
232 ms |
219516 KB |
Output is correct |
4 |
Correct |
235 ms |
219640 KB |
Output is correct |
5 |
Correct |
234 ms |
219540 KB |
Output is correct |
6 |
Correct |
234 ms |
219504 KB |
Output is correct |
7 |
Correct |
233 ms |
219516 KB |
Output is correct |
8 |
Correct |
234 ms |
219640 KB |
Output is correct |
9 |
Correct |
233 ms |
219776 KB |
Output is correct |
10 |
Correct |
233 ms |
219828 KB |
Output is correct |
11 |
Correct |
234 ms |
219768 KB |
Output is correct |
12 |
Correct |
238 ms |
219768 KB |
Output is correct |
13 |
Correct |
227 ms |
219948 KB |
Output is correct |
14 |
Correct |
234 ms |
219888 KB |
Output is correct |
15 |
Correct |
230 ms |
219752 KB |
Output is correct |
16 |
Correct |
233 ms |
220696 KB |
Output is correct |
17 |
Correct |
267 ms |
227288 KB |
Output is correct |
18 |
Correct |
300 ms |
239096 KB |
Output is correct |
19 |
Correct |
314 ms |
242048 KB |
Output is correct |
20 |
Correct |
318 ms |
242040 KB |
Output is correct |
21 |
Correct |
238 ms |
223224 KB |
Output is correct |
22 |
Correct |
308 ms |
239608 KB |
Output is correct |
23 |
Correct |
303 ms |
237344 KB |
Output is correct |
24 |
Correct |
318 ms |
241056 KB |
Output is correct |
25 |
Correct |
321 ms |
242040 KB |
Output is correct |
26 |
Correct |
324 ms |
242040 KB |
Output is correct |
27 |
Correct |
313 ms |
242228 KB |
Output is correct |
28 |
Correct |
322 ms |
242092 KB |
Output is correct |
29 |
Correct |
325 ms |
242024 KB |
Output is correct |
30 |
Correct |
318 ms |
242052 KB |
Output is correct |
31 |
Correct |
342 ms |
242040 KB |
Output is correct |
32 |
Correct |
318 ms |
242140 KB |
Output is correct |
33 |
Correct |
354 ms |
242040 KB |
Output is correct |
34 |
Correct |
352 ms |
242296 KB |
Output is correct |
35 |
Correct |
324 ms |
235896 KB |
Output is correct |
36 |
Correct |
282 ms |
231416 KB |
Output is correct |
37 |
Correct |
371 ms |
242296 KB |
Output is correct |
38 |
Correct |
366 ms |
242936 KB |
Output is correct |
39 |
Correct |
366 ms |
242956 KB |
Output is correct |
40 |
Correct |
369 ms |
242808 KB |
Output is correct |
41 |
Correct |
366 ms |
242904 KB |
Output is correct |
42 |
Correct |
319 ms |
242192 KB |
Output is correct |
43 |
Correct |
318 ms |
242276 KB |
Output is correct |
44 |
Correct |
316 ms |
242344 KB |
Output is correct |
45 |
Correct |
446 ms |
242936 KB |
Output is correct |
46 |
Correct |
438 ms |
243136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
219700 KB |
Output is correct |
2 |
Correct |
246 ms |
219512 KB |
Output is correct |
3 |
Correct |
227 ms |
219560 KB |
Output is correct |
4 |
Correct |
236 ms |
219512 KB |
Output is correct |
5 |
Correct |
228 ms |
219592 KB |
Output is correct |
6 |
Correct |
231 ms |
219456 KB |
Output is correct |
7 |
Correct |
229 ms |
219548 KB |
Output is correct |
8 |
Correct |
233 ms |
219612 KB |
Output is correct |
9 |
Correct |
230 ms |
219640 KB |
Output is correct |
10 |
Correct |
229 ms |
219768 KB |
Output is correct |
11 |
Correct |
235 ms |
219896 KB |
Output is correct |
12 |
Correct |
234 ms |
219868 KB |
Output is correct |
13 |
Correct |
238 ms |
219912 KB |
Output is correct |
14 |
Correct |
236 ms |
219768 KB |
Output is correct |
15 |
Correct |
236 ms |
219864 KB |
Output is correct |
16 |
Correct |
240 ms |
220664 KB |
Output is correct |
17 |
Correct |
267 ms |
227292 KB |
Output is correct |
18 |
Correct |
308 ms |
239232 KB |
Output is correct |
19 |
Correct |
318 ms |
242040 KB |
Output is correct |
20 |
Correct |
319 ms |
242124 KB |
Output is correct |
21 |
Correct |
246 ms |
223092 KB |
Output is correct |
22 |
Correct |
307 ms |
239480 KB |
Output is correct |
23 |
Correct |
303 ms |
237424 KB |
Output is correct |
24 |
Correct |
318 ms |
240828 KB |
Output is correct |
25 |
Correct |
320 ms |
242040 KB |
Output is correct |
26 |
Correct |
330 ms |
242052 KB |
Output is correct |
27 |
Correct |
311 ms |
242040 KB |
Output is correct |
28 |
Correct |
324 ms |
242040 KB |
Output is correct |
29 |
Correct |
335 ms |
242112 KB |
Output is correct |
30 |
Correct |
317 ms |
242056 KB |
Output is correct |
31 |
Correct |
321 ms |
242168 KB |
Output is correct |
32 |
Correct |
323 ms |
242040 KB |
Output is correct |
33 |
Correct |
369 ms |
242176 KB |
Output is correct |
34 |
Correct |
348 ms |
242164 KB |
Output is correct |
35 |
Correct |
315 ms |
235896 KB |
Output is correct |
36 |
Correct |
276 ms |
231504 KB |
Output is correct |
37 |
Correct |
366 ms |
242300 KB |
Output is correct |
38 |
Correct |
365 ms |
242972 KB |
Output is correct |
39 |
Correct |
363 ms |
242768 KB |
Output is correct |
40 |
Correct |
363 ms |
242808 KB |
Output is correct |
41 |
Correct |
367 ms |
242880 KB |
Output is correct |
42 |
Correct |
327 ms |
242300 KB |
Output is correct |
43 |
Correct |
325 ms |
242260 KB |
Output is correct |
44 |
Correct |
325 ms |
242296 KB |
Output is correct |
45 |
Correct |
449 ms |
243096 KB |
Output is correct |
46 |
Correct |
455 ms |
242980 KB |
Output is correct |
47 |
Runtime error |
439 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
48 |
Halted |
0 ms |
0 KB |
- |