#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
const int sz = 100;
int dist[30005];
int brr[30005][105];
vector <int> stuf[30005];
int S[30005], P[30005], proc[30005];
void solve(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int a, b; cin >> a >> b;
stuf[a].push_back(b);
S[i] = a, P[i] = b;
}
for(int i=0;i<n;i++)for(int j=0;j<=sz;j++)brr[i][j] = 1e18;
for(int i=0;i<n;i++)dist[i] = 1e18;
queue <pi> q;
q.push({S[1], -1});
dist[S[1]] = 0;
while(!q.empty()){
int x = q.front().fi, y = q.front().se; q.pop();
if(y != -1){
if(x + y < n && brr[x + y][y] > brr[x][y] + 1)brr[x + y][y] = brr[x][y] + 1, dist[x + y] = min(dist[x + y], brr[x][y] + 1), q.push({x + y, y});
if(x - y >= 0 && brr[x-y][y] > brr[x][y] + 1)brr[x-y][y] = brr[x][y] + 1, dist[x-y] = min(dist[x-y], brr[x][y] + 1), q.push({x-y, y});
}
if(!proc[x]){
proc[x] = 1;
for(auto i : stuf[x]){
if(i > sz){
for(int j = x + i; j < n; j += i){
if(dist[j] > dist[x] + (j - x) / i)dist[j] = dist[x] + (j - x) / i, q.push({j, -1});
}
for(int j = x - i; j >= 0; j -= i){
if(dist[j] > dist[x] + (x - j) / i)dist[j] = dist[x] + (x - j) / i, q.push({j, -1});
}
}
else{
y = i;
if(x + y < n && brr[x + y][y] > dist[x] + 1)brr[x + y][y] = dist[x] + 1, dist[x + y] = min(dist[x + y], dist[x] + 1), q.push({x + y, y});
if(x - y >= 0 && brr[x-y][y] > dist[x] + 1)brr[x-y][y] = dist[x] + 1, dist[x-y] = min(dist[x-y], dist[x] + 1), q.push({x-y, y});
}
}
}
}
cout << (dist[S[2]] == 1e18 ? -1 : dist[S[2]]);
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
skyscraper.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
61 | main(){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1108 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
1 ms |
1236 KB |
Output is correct |
12 |
Correct |
1 ms |
1172 KB |
Output is correct |
13 |
Correct |
1 ms |
1108 KB |
Output is correct |
14 |
Correct |
1 ms |
1176 KB |
Output is correct |
15 |
Correct |
1 ms |
1172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
1040 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1108 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
1108 KB |
Output is correct |
13 |
Correct |
1 ms |
1176 KB |
Output is correct |
14 |
Correct |
1 ms |
1236 KB |
Output is correct |
15 |
Correct |
1 ms |
1236 KB |
Output is correct |
16 |
Correct |
1 ms |
1236 KB |
Output is correct |
17 |
Correct |
1 ms |
1748 KB |
Output is correct |
18 |
Correct |
1 ms |
2516 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2972 KB |
Output is correct |
21 |
Correct |
1 ms |
1364 KB |
Output is correct |
22 |
Correct |
1 ms |
2516 KB |
Output is correct |
23 |
Correct |
1 ms |
2388 KB |
Output is correct |
24 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1040 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
1 ms |
1236 KB |
Output is correct |
12 |
Correct |
1 ms |
1108 KB |
Output is correct |
13 |
Correct |
1 ms |
1108 KB |
Output is correct |
14 |
Correct |
1 ms |
1172 KB |
Output is correct |
15 |
Correct |
1 ms |
1236 KB |
Output is correct |
16 |
Correct |
1 ms |
1236 KB |
Output is correct |
17 |
Correct |
2 ms |
1692 KB |
Output is correct |
18 |
Correct |
2 ms |
2456 KB |
Output is correct |
19 |
Correct |
1 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2772 KB |
Output is correct |
21 |
Correct |
1 ms |
1428 KB |
Output is correct |
22 |
Correct |
1 ms |
2516 KB |
Output is correct |
23 |
Correct |
1 ms |
2388 KB |
Output is correct |
24 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
960 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
1040 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1108 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
1 ms |
1236 KB |
Output is correct |
12 |
Correct |
2 ms |
1176 KB |
Output is correct |
13 |
Correct |
1 ms |
1108 KB |
Output is correct |
14 |
Correct |
1 ms |
1236 KB |
Output is correct |
15 |
Correct |
1 ms |
1180 KB |
Output is correct |
16 |
Correct |
1 ms |
1236 KB |
Output is correct |
17 |
Correct |
2 ms |
1748 KB |
Output is correct |
18 |
Correct |
1 ms |
2460 KB |
Output is correct |
19 |
Correct |
1 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2848 KB |
Output is correct |
21 |
Correct |
1 ms |
1364 KB |
Output is correct |
22 |
Correct |
1 ms |
2516 KB |
Output is correct |
23 |
Correct |
1 ms |
2388 KB |
Output is correct |
24 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |