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 mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define Scan(a) scanf ("%I64d", &a)
#define scan(a) scanf ("%d", &a)
#define int long long
using namespace std;
const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;
priority_queue<pair<int,int >> q;
int b[N], p[N], vis[N];
vector<int > v[N];
main () {
int n, m;
cin >> n >> m;
for(int i = 1;i <= m; i++){
cin >> b[i] >> p[i];
v[b[i]].pb(p[i]);
}
memset(vis, 0x3f3f3f3f, sizeof(vis));
vis[b[1]] = 0;
q.push(mk(0,b[1]));
while(!q.empty()){
pair<int,int > u = q.top();
q.pop();
for(auto i : v[u.sc]){
int cnt = u.fr;
for(int j = u.sc + i; j < n; j += i){
if(vis[j] > ++cnt){
q.push(mk(vis[j] = cnt,j));
}
}
cnt = u.fr;
for(int j = u.sc - i; j >= 0; j -= i){
if(vis[j] > ++cnt){
q.push(mk(vis[j] = cnt,j));
}
}
}
}
int ans = vis[b[2]];
cout << ((ans > 1e9) ? -1 : ans);
}
Compilation message (stderr)
skyscraper.cpp:21:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
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... |