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>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 3e4 + 100;
int N, M, St, En;
vector<int> List[MAX_N];
int main() {
cin >> N >> M;
REP(i, M) {
int x, p; scanf("%d%d", &x, &p);
if(i == 0) St = x;
if(i == 1) En = x;
List[x].push_back(p);
}
for(int i=0; i<N; i++) {
sort(ALL(List[i]));
List[i].erase(unique(ALL(List[i])), List[i].end());
}
priority_queue<pi, vector<pi>, greater<pi> > Q;
vector<int> dis(N+1, INF);
Q.push(pi(0, St)); dis[St] = 0;
while(!Q.empty()) {
int d, x; tie(d, x) = Q.top(); Q.pop();
if(dis[x] < d) continue;
for(int p : List[x]) {
for(int i=x+p, cnt=1; i<N; i+=p, cnt++) {
if(dis[i] > d+cnt)
Q.push(pi(dis[i] = d+cnt, i));
int ix = lower_bound(ALL(List[i]), p) - List[i].begin();
if(ix < SZ(List[i]) && List[i][ix] == p) break;
}
for(int i=x-p, cnt=1; i>=0; i-=p, cnt++) {
if(dis[i] > d+cnt)
Q.push(pi(dis[i] = d+cnt, i));
int ix = lower_bound(ALL(List[i]), p) - List[i].begin();
if(ix < SZ(List[i]) && List[i][ix] == p) break;
}
}
}
if(dis[En] == INF) dis[En] = -1;
printf("%d\n", dis[En]);
return 0;
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, p; scanf("%d%d", &x, &p);
^
# | 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... |