#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 3e4 + 5;
const int SQ = 100;
vector<int> adj1[N][SQ];
vector<int> adj11[N][SQ];
vector<pair<int,int>> r_adj1[N];
vector<pair<int,int>> adj2[N];
vector<int> r_adj2[N];
ll dis[3][N][SQ];
void solve(){
int n,m;
cin>>n>>m;
vector<pair<int,int>> d(m);
for(auto &[i,p] : d) cin>>i>>p;
vector<vector<int>> dogs(n+1);
for(int i=0;i<m;i++) dogs[d[i].first].push_back(i);
for(int i=0;i<n;i++){
for(int j=1;j<SQ;j++){
adj1[i][j].push_back(i);
if(i+j<n) adj11[i][j].push_back(i+j) ;
if(i-j>=0) adj11[i][j].push_back(i-j);
}
}
for(int i=0;i<n;i++){
for(auto j : dogs[i]){
if(d[j].second < SQ) r_adj1[i].push_back({d[j].first,d[j].second});
else r_adj2[i].push_back(j);
}
}
for(int j=0;j<m;j++){
auto [i,p] = d[j];
if(p < SQ) continue;
for(int k=i+p;k<n;k+=p) adj2[j].push_back({k,(k-i)/p});
for(int k=i-p;k>=0;k-=p) adj2[j].push_back({k,(i-k)/p});
}
priority_queue<array<ll,4>,vector<array<ll,4>>,greater<>> q;
for(int i=0;i<N;i++) for(int j=0;j<=SQ;j++) dis[0][i][j] = dis[1][i][j] = dis[2][i][j] = 1e18;
dis[0][d[0].first][0] = 0;
q.push({0,0,d[0].first,0});
while(q.size()){
auto [c,t,i,p] = q.top(); q.pop();
if(c > dis[t][i][p]) continue;
if(t == 0){
for(auto [ii,pp] : r_adj1[i]){
if(c < dis[1][ii][pp]) {
//cout<<"HI"<<endl;
q.push({c,1,ii,pp});
dis[1][ii][pp] = c;
}
}
for(auto j : r_adj2[i]){
if(c < dis[2][j][0]){
q.push({c,2,j,0});
dis[2][j][0] = c;
}
}
}
else if(t == 1){
//if(t == 1 && i == 4 && p == 1) cout<<"WOW"<<endl;
for(auto j : adj1[i][p]){
if(c < dis[0][j][0]){
//if(i == 0 && p == 2) cout<<j<<endl;
q.push({c,0,j,0});
dis[0][j][0] = c;
}
}
for(auto j : adj11[i][p]){
//if(t == 1 && i == 4 && p == 1) cout<<"mm"<<endl;
if(c+1 < dis[1][j][p]){
//if(t == 1 && i == 4 && p == 1) cout<<j<<' '<<p<<endl;
q.push({c+1,1,j,p});
dis[1][j][p] = c+1;
}
}
}
else {
for(auto [j,cost] : adj2[i]){
if(c + cost < dis[0][j][0]){
q.push({c+cost,0,j,0});
dis[0][j][0] = c + cost;
}
}
}
}
cout<<(dis[0][d[1].first][0] == 1e18 ? -1 : dis[0][d[1].first][0])<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
18 | for(auto &[i,p] : d) cin>>i>>p;
| ^
skyscraper.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | auto [i,p] = d[j];
| ^
skyscraper.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | auto [c,t,i,p] = q.top(); q.pop();
| ^
skyscraper.cpp:49:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for(auto [ii,pp] : r_adj1[i]){
| ^
skyscraper.cpp:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for(auto [j,cost] : adj2[i]){
| ^
skyscraper.cpp:42:92: warning: iteration 100 invokes undefined behavior [-Waggressive-loop-optimizations]
42 | for(int i=0;i<N;i++) for(int j=0;j<=SQ;j++) dis[0][i][j] = dis[1][i][j] = dis[2][i][j] = 1e18;
| ~~~~~~~~~~~~~^~~~~~
skyscraper.cpp:42:39: note: within this loop
42 | for(int i=0;i<N;i++) for(int j=0;j<=SQ;j++) dis[0][i][j] = dis[1][i][j] = dis[2][i][j] = 1e18;
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
340 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
329 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
334 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
325 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
337 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
