This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;
template <typename T> inline void Read(T &x){
x = 0; char c;
ll dau = 1;
while(!isdigit(c = getchar())) if(c == '-') dau = -1;
do{
x = x * 10 + c - '0';
} while (isdigit(c = getchar()));
x *= dau;
}
ll read(){
ll tmp;
cin >> tmp;
return tmp;
}
void giuncute(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
void OF(){
if(fopen(Fname".inp", "r")){
freopen(Fname".inp", "r", stdin);
freopen(Fname".out", "w", stdout);
} else if(fopen(Fname".in", "r")){
freopen(Fname".in", "r", stdin);
freopen(Fname".out", "w", stdout);
}
}
cll mxn = 3e4 + 5, _sqrt = 173;
ll n, m, dp[mxn][_sqrt + 4];
vec(ll) jump[mxn];
priority_queue<pp(ll, pp(ll, ll))> q;
void prc(ll u, ll cu, ll step){
if(u + step < n && dp[u + step][step] > cu + 1){
dp[u + step][step] = cu + 1;
q.push({-dp[u + step][step], {u + step, step}});
}
if(u - step >= 0 && dp[u - step][step] > cu + 1){
dp[u - step][step] = cu + 1;
q.push({-dp[u - step][step], {u - step, step}});
}
if(u + step < n && dp[u + step][0] > cu + 1){
dp[u + step][0] = cu + 1;
q.push({-dp[u + step][0], {u + step, 0}});
}
if(u - step >= 0 && dp[u - step][0] > cu + 1){
dp[u - step][0] = cu + 1;
q.push({-dp[u - step][0], {u - step, 0}});
}
}
int main(){
giuncute();
#ifndef ONLINE_JUDGE
// OF();
// freopen("test.inp","r",stdin);
#endif
cin >> n >> m;
int st,ed;
lp(i, 1, m){
static ll u, p;
cin >> u >> p;
if (i==1) st=u;
if (i==m) ed=u;
jump[u].push_back(p);
}
if (n==1)
{
cout<<-1;
return 0;
}
lp(i, 0, n) lp(j, 0, _sqrt) dp[i][j] = 1e16;
lp(i, 0, _sqrt) dp[st][i] = 0;
q.push({0, {st, 0}});
while(q.size()){
ll cu = -q.top().first, u = q.top().second.first, step = q.top().second.second;
q.pop();
if(cu != dp[u][step]) continue;
// maintain last step
prc(u, cu, step);
// change step
for(ll i : jump[u]){
if(i <= _sqrt)
prc(u, cu, i);
else{
for(ll v = u + i, cnt = 1; v < n; v += i, ++cnt)
if(dp[v][0] > cu + cnt){
dp[v][0] = cu + cnt;
q.push({-dp[v][0], {v, 0}});
}
for(ll v = u - i, cnt = 1; v >= 0; v -= i, ++cnt)
if(dp[v][0] > cu + cnt){
dp[v][0] = cu + cnt;
q.push({-dp[v][0], {v, 0}});
}
}
}
}
ll ans = 1e16;
lp(i, 0, _sqrt) ans = min(ans, dp[ed][i]);
if(ans > 1e15) ans = -1;
cout << ans;
}
Compilation message (stderr)
skyscraper.cpp: In function 'void OF()':
skyscraper.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen(Fname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen(Fname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen(Fname".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen(Fname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:78:12: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | int st,ed;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |