This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 3e4+5, mod = 1e9+7, sq = 500;
int n,m;
set<pair<int,int>>s;
int D[N];
int X[N],P[N];
int F[N];
vector<int>V[N];
inline void test_case(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>X[i]>>P[i];
X[i]++;
V[X[i]].push_back(i);
}
for(int i=1;i<=m;i++){
if(i>1){
D[i] = 1e9;
//s.insert({1e9,i});
}
}
D[1] = 0;
F[X[1]] = 1;
s.insert({0,1});
while(s.size()){
pair<int,int> p = *(s.begin());
s.erase(s.begin());
int i = p.second;
int dist = p.first;
F[X[i]] = 1;
if(i==2){
if(D[2]==1e9)D[2]=-1;
cout<<D[2]<<endl;
return ;
}
for(int j=X[i];j<=n;j+=P[i]){
if(F[j] && j != X[i]) continue;
for(int k=0;k<V[j].size();k++){
int to = V[j][k];
if(D[to] > dist + (j-X[i])/P[i] || D[to]==1e9){
if(D[to]!=1e9)
s.erase({D[to],to});
D[to] = dist + (j-X[i])/P[i];
s.insert({D[to],to});
}
}
}
for(int j=X[i]-P[i];j>=1;j-=P[i]){
if(F[j]) continue;
for(int k=0;k<V[j].size();k++){
int to = V[j][k];
if(D[to] > dist + (X[i]-j)/P[i] || D[to] == 1e9){
if(D[to]!=1e9)
s.erase({D[to],to});
D[to] = dist + (X[i]-j)/P[i];
s.insert({D[to],to});
}
}
}
}
if(D[2]==1e9)
D[2] = -1;
cout<<D[2]<<endl;
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
while(T--){
test_case();
}
}
Compilation message (stderr)
skyscraper.cpp: In function 'void test_case()':
skyscraper.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int k=0;k<V[j].size();k++){
| ~^~~~~~~~~~~~
skyscraper.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int k=0;k<V[j].size();k++){
| ~^~~~~~~~~~~~
skyscraper.cpp: At global scope:
skyscraper.cpp:89:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
89 | main(){
| ^
# | 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... |