#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define ALL(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 2e6 + 5;
int N, M, source, sink;
vector <pair <int, int>> ke[MAXN];
int dp[MAXN];
int ID(int x, int y) {
return (x - 1) * 30 + y;
}
void solve(void) {
cin >> N >> M;
For (i, 1, M) {
int b, q; cin >> b >> q; b++;
if(i == 1) source = b;
if(i == 2) sink = b;
if(q >= 30) {
for (int j = b - q; j >= 1; j -= q) ke[b].push_back(make_pair(j, (b - j) / q));
for (int j = b + q; j <= N; j += q) ke[b].push_back(make_pair(j, (j - b) / q));
} else ke[b].push_back(make_pair(N + ID(b, q), 0));
}
For (i, 1, N) For (j, 1, 30) {
ke[N + ID(i, j)].push_back(make_pair(i, 0));
}
For (i, 1, N) For (j, 1, 30) if(i + j <= N) {
ke[N + ID(i, j)].push_back(make_pair(N + ID(i + j, j), 1));
ke[N + ID(i + j, j)].push_back(make_pair(N + ID(i, j), 1));
}
memset(dp, 0x3f, sizeof(dp));
dp[source] = 0;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
heap.push(make_pair(0, source));
while(heap.size()) {
int u = heap.top().second; heap.pop();
for (auto v : ke[u]) if(minimize(dp[v.first], dp[u] + v.second)) {
heap.push(make_pair(dp[v.first], v.first));
}
}
cout << (dp[sink] >= 1e9 ? -1 : dp[sink]);
}
signed main() {
file("TASK");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test; test = 1;
// cin >> test;
while(test--){
solve();
cout << '\n';
}
// cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:61:5: note: in expansion of macro 'file'
61 | file("TASK");
| ^~~~
skyscraper.cpp:14:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:61:5: note: in expansion of macro 'file'
61 | file("TASK");
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
55068 KB |
Output is correct |
2 |
Correct |
36 ms |
55108 KB |
Output is correct |
3 |
Correct |
30 ms |
55124 KB |
Output is correct |
4 |
Correct |
31 ms |
55124 KB |
Output is correct |
5 |
Correct |
32 ms |
55096 KB |
Output is correct |
6 |
Correct |
33 ms |
55112 KB |
Output is correct |
7 |
Correct |
31 ms |
55100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
55124 KB |
Output is correct |
2 |
Correct |
32 ms |
55100 KB |
Output is correct |
3 |
Correct |
36 ms |
55008 KB |
Output is correct |
4 |
Correct |
31 ms |
55124 KB |
Output is correct |
5 |
Correct |
35 ms |
55036 KB |
Output is correct |
6 |
Correct |
34 ms |
55124 KB |
Output is correct |
7 |
Correct |
37 ms |
55084 KB |
Output is correct |
8 |
Correct |
38 ms |
55100 KB |
Output is correct |
9 |
Correct |
34 ms |
55092 KB |
Output is correct |
10 |
Correct |
34 ms |
55296 KB |
Output is correct |
11 |
Correct |
35 ms |
55212 KB |
Output is correct |
12 |
Correct |
37 ms |
55224 KB |
Output is correct |
13 |
Correct |
32 ms |
55320 KB |
Output is correct |
14 |
Correct |
35 ms |
55236 KB |
Output is correct |
15 |
Correct |
34 ms |
55244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
55100 KB |
Output is correct |
2 |
Correct |
34 ms |
55032 KB |
Output is correct |
3 |
Correct |
36 ms |
54988 KB |
Output is correct |
4 |
Correct |
40 ms |
55020 KB |
Output is correct |
5 |
Correct |
36 ms |
55112 KB |
Output is correct |
6 |
Correct |
37 ms |
55108 KB |
Output is correct |
7 |
Correct |
38 ms |
55044 KB |
Output is correct |
8 |
Correct |
34 ms |
55084 KB |
Output is correct |
9 |
Correct |
36 ms |
55212 KB |
Output is correct |
10 |
Correct |
35 ms |
55216 KB |
Output is correct |
11 |
Correct |
36 ms |
55252 KB |
Output is correct |
12 |
Correct |
38 ms |
55232 KB |
Output is correct |
13 |
Correct |
35 ms |
55256 KB |
Output is correct |
14 |
Correct |
36 ms |
55324 KB |
Output is correct |
15 |
Correct |
41 ms |
55276 KB |
Output is correct |
16 |
Correct |
38 ms |
55380 KB |
Output is correct |
17 |
Correct |
42 ms |
56156 KB |
Output is correct |
18 |
Correct |
44 ms |
57536 KB |
Output is correct |
19 |
Correct |
45 ms |
57964 KB |
Output is correct |
20 |
Correct |
48 ms |
57956 KB |
Output is correct |
21 |
Correct |
37 ms |
55624 KB |
Output is correct |
22 |
Correct |
52 ms |
57720 KB |
Output is correct |
23 |
Correct |
45 ms |
57456 KB |
Output is correct |
24 |
Correct |
44 ms |
57868 KB |
Output is correct |
25 |
Correct |
45 ms |
57940 KB |
Output is correct |
26 |
Correct |
48 ms |
57932 KB |
Output is correct |
27 |
Correct |
44 ms |
57984 KB |
Output is correct |
28 |
Correct |
43 ms |
58092 KB |
Output is correct |
29 |
Correct |
54 ms |
58304 KB |
Output is correct |
30 |
Correct |
51 ms |
57900 KB |
Output is correct |
31 |
Correct |
42 ms |
58332 KB |
Output is correct |
32 |
Correct |
53 ms |
58064 KB |
Output is correct |
33 |
Correct |
68 ms |
58776 KB |
Output is correct |
34 |
Correct |
62 ms |
58784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
54992 KB |
Output is correct |
2 |
Correct |
40 ms |
54988 KB |
Output is correct |
3 |
Correct |
34 ms |
55092 KB |
Output is correct |
4 |
Correct |
34 ms |
55032 KB |
Output is correct |
5 |
Correct |
36 ms |
55096 KB |
Output is correct |
6 |
Correct |
34 ms |
55092 KB |
Output is correct |
7 |
Correct |
34 ms |
55024 KB |
Output is correct |
8 |
Correct |
33 ms |
55176 KB |
Output is correct |
9 |
Correct |
35 ms |
55192 KB |
Output is correct |
10 |
Correct |
34 ms |
55216 KB |
Output is correct |
11 |
Correct |
34 ms |
55288 KB |
Output is correct |
12 |
Correct |
33 ms |
55292 KB |
Output is correct |
13 |
Correct |
31 ms |
55232 KB |
Output is correct |
14 |
Correct |
34 ms |
55240 KB |
Output is correct |
15 |
Correct |
35 ms |
55320 KB |
Output is correct |
16 |
Correct |
35 ms |
55364 KB |
Output is correct |
17 |
Correct |
42 ms |
56256 KB |
Output is correct |
18 |
Correct |
54 ms |
57612 KB |
Output is correct |
19 |
Correct |
45 ms |
57864 KB |
Output is correct |
20 |
Correct |
40 ms |
57996 KB |
Output is correct |
21 |
Correct |
31 ms |
55628 KB |
Output is correct |
22 |
Correct |
41 ms |
57716 KB |
Output is correct |
23 |
Correct |
44 ms |
57444 KB |
Output is correct |
24 |
Correct |
45 ms |
57800 KB |
Output is correct |
25 |
Correct |
45 ms |
57912 KB |
Output is correct |
26 |
Correct |
43 ms |
57932 KB |
Output is correct |
27 |
Correct |
47 ms |
57988 KB |
Output is correct |
28 |
Correct |
49 ms |
58128 KB |
Output is correct |
29 |
Correct |
50 ms |
58228 KB |
Output is correct |
30 |
Correct |
50 ms |
58060 KB |
Output is correct |
31 |
Correct |
44 ms |
58280 KB |
Output is correct |
32 |
Correct |
42 ms |
58060 KB |
Output is correct |
33 |
Correct |
50 ms |
58696 KB |
Output is correct |
34 |
Correct |
51 ms |
58688 KB |
Output is correct |
35 |
Correct |
60 ms |
58060 KB |
Output is correct |
36 |
Correct |
43 ms |
56824 KB |
Output is correct |
37 |
Correct |
58 ms |
59504 KB |
Output is correct |
38 |
Correct |
53 ms |
59324 KB |
Output is correct |
39 |
Correct |
53 ms |
59340 KB |
Output is correct |
40 |
Correct |
53 ms |
59412 KB |
Output is correct |
41 |
Correct |
55 ms |
59392 KB |
Output is correct |
42 |
Correct |
54 ms |
58440 KB |
Output is correct |
43 |
Correct |
47 ms |
58444 KB |
Output is correct |
44 |
Correct |
53 ms |
58444 KB |
Output is correct |
45 |
Correct |
68 ms |
62084 KB |
Output is correct |
46 |
Correct |
60 ms |
62112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
54988 KB |
Output is correct |
2 |
Correct |
34 ms |
55044 KB |
Output is correct |
3 |
Correct |
36 ms |
55016 KB |
Output is correct |
4 |
Correct |
38 ms |
55020 KB |
Output is correct |
5 |
Correct |
35 ms |
55104 KB |
Output is correct |
6 |
Correct |
34 ms |
55072 KB |
Output is correct |
7 |
Correct |
33 ms |
55036 KB |
Output is correct |
8 |
Correct |
34 ms |
55168 KB |
Output is correct |
9 |
Correct |
33 ms |
55196 KB |
Output is correct |
10 |
Correct |
34 ms |
55296 KB |
Output is correct |
11 |
Correct |
39 ms |
55240 KB |
Output is correct |
12 |
Correct |
31 ms |
55264 KB |
Output is correct |
13 |
Correct |
36 ms |
55244 KB |
Output is correct |
14 |
Correct |
36 ms |
55260 KB |
Output is correct |
15 |
Correct |
33 ms |
55240 KB |
Output is correct |
16 |
Correct |
33 ms |
55472 KB |
Output is correct |
17 |
Correct |
36 ms |
56264 KB |
Output is correct |
18 |
Correct |
40 ms |
57676 KB |
Output is correct |
19 |
Correct |
42 ms |
57924 KB |
Output is correct |
20 |
Correct |
44 ms |
57984 KB |
Output is correct |
21 |
Correct |
39 ms |
55732 KB |
Output is correct |
22 |
Correct |
42 ms |
57708 KB |
Output is correct |
23 |
Correct |
42 ms |
57456 KB |
Output is correct |
24 |
Correct |
44 ms |
57804 KB |
Output is correct |
25 |
Correct |
42 ms |
57916 KB |
Output is correct |
26 |
Correct |
42 ms |
58012 KB |
Output is correct |
27 |
Correct |
47 ms |
57932 KB |
Output is correct |
28 |
Correct |
44 ms |
58080 KB |
Output is correct |
29 |
Correct |
68 ms |
58288 KB |
Output is correct |
30 |
Correct |
45 ms |
57948 KB |
Output is correct |
31 |
Correct |
41 ms |
58316 KB |
Output is correct |
32 |
Correct |
41 ms |
58068 KB |
Output is correct |
33 |
Correct |
50 ms |
58788 KB |
Output is correct |
34 |
Correct |
50 ms |
58672 KB |
Output is correct |
35 |
Correct |
46 ms |
57996 KB |
Output is correct |
36 |
Correct |
37 ms |
56756 KB |
Output is correct |
37 |
Correct |
55 ms |
59568 KB |
Output is correct |
38 |
Correct |
58 ms |
59340 KB |
Output is correct |
39 |
Correct |
62 ms |
59312 KB |
Output is correct |
40 |
Correct |
55 ms |
59372 KB |
Output is correct |
41 |
Correct |
56 ms |
59452 KB |
Output is correct |
42 |
Correct |
45 ms |
58408 KB |
Output is correct |
43 |
Correct |
45 ms |
58448 KB |
Output is correct |
44 |
Correct |
48 ms |
58440 KB |
Output is correct |
45 |
Correct |
66 ms |
62056 KB |
Output is correct |
46 |
Correct |
56 ms |
62184 KB |
Output is correct |
47 |
Correct |
174 ms |
79176 KB |
Output is correct |
48 |
Correct |
144 ms |
89544 KB |
Output is correct |
49 |
Correct |
168 ms |
92372 KB |
Output is correct |
50 |
Correct |
167 ms |
95644 KB |
Output is correct |
51 |
Correct |
229 ms |
100248 KB |
Output is correct |
52 |
Correct |
232 ms |
100420 KB |
Output is correct |
53 |
Correct |
193 ms |
97848 KB |
Output is correct |
54 |
Correct |
175 ms |
97284 KB |
Output is correct |
55 |
Correct |
189 ms |
97360 KB |
Output is correct |
56 |
Correct |
177 ms |
98504 KB |
Output is correct |
57 |
Correct |
345 ms |
104840 KB |
Output is correct |
58 |
Correct |
170 ms |
97880 KB |
Output is correct |
59 |
Correct |
187 ms |
98100 KB |
Output is correct |
60 |
Correct |
207 ms |
98644 KB |
Output is correct |
61 |
Correct |
203 ms |
98096 KB |
Output is correct |
62 |
Correct |
209 ms |
101124 KB |
Output is correct |
63 |
Correct |
227 ms |
120112 KB |
Output is correct |
64 |
Correct |
231 ms |
125672 KB |
Output is correct |
65 |
Correct |
281 ms |
133532 KB |
Output is correct |
66 |
Correct |
459 ms |
154348 KB |
Output is correct |
67 |
Correct |
460 ms |
154156 KB |
Output is correct |