#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, N) {
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();
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
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 |
1 |
Correct |
0 ms |
2728 KB |
Output is correct |
2 |
Correct |
0 ms |
2728 KB |
Output is correct |
3 |
Correct |
0 ms |
2728 KB |
Output is correct |
4 |
Correct |
0 ms |
2728 KB |
Output is correct |
5 |
Correct |
0 ms |
2728 KB |
Output is correct |
6 |
Correct |
0 ms |
2728 KB |
Output is correct |
7 |
Correct |
0 ms |
2728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2728 KB |
Output is correct |
2 |
Correct |
0 ms |
2728 KB |
Output is correct |
3 |
Correct |
0 ms |
2728 KB |
Output is correct |
4 |
Correct |
0 ms |
2728 KB |
Output is correct |
5 |
Correct |
0 ms |
2728 KB |
Output is correct |
6 |
Correct |
0 ms |
2728 KB |
Output is correct |
7 |
Correct |
0 ms |
2728 KB |
Output is correct |
8 |
Correct |
0 ms |
2728 KB |
Output is correct |
9 |
Correct |
0 ms |
2728 KB |
Output is correct |
10 |
Incorrect |
0 ms |
2728 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2728 KB |
Output is correct |
2 |
Correct |
0 ms |
2728 KB |
Output is correct |
3 |
Correct |
0 ms |
2728 KB |
Output is correct |
4 |
Correct |
0 ms |
2728 KB |
Output is correct |
5 |
Correct |
0 ms |
2728 KB |
Output is correct |
6 |
Correct |
0 ms |
2728 KB |
Output is correct |
7 |
Correct |
0 ms |
2728 KB |
Output is correct |
8 |
Correct |
0 ms |
2728 KB |
Output is correct |
9 |
Correct |
0 ms |
2728 KB |
Output is correct |
10 |
Incorrect |
0 ms |
2728 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2728 KB |
Output is correct |
2 |
Correct |
0 ms |
2728 KB |
Output is correct |
3 |
Correct |
0 ms |
2728 KB |
Output is correct |
4 |
Correct |
0 ms |
2728 KB |
Output is correct |
5 |
Correct |
0 ms |
2728 KB |
Output is correct |
6 |
Correct |
0 ms |
2728 KB |
Output is correct |
7 |
Correct |
0 ms |
2728 KB |
Output is correct |
8 |
Correct |
0 ms |
2728 KB |
Output is correct |
9 |
Correct |
0 ms |
2728 KB |
Output is correct |
10 |
Incorrect |
0 ms |
2728 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2728 KB |
Output is correct |
2 |
Correct |
0 ms |
2728 KB |
Output is correct |
3 |
Correct |
0 ms |
2728 KB |
Output is correct |
4 |
Correct |
0 ms |
2728 KB |
Output is correct |
5 |
Correct |
0 ms |
2728 KB |
Output is correct |
6 |
Correct |
0 ms |
2728 KB |
Output is correct |
7 |
Correct |
0 ms |
2728 KB |
Output is correct |
8 |
Correct |
0 ms |
2728 KB |
Output is correct |
9 |
Correct |
0 ms |
2728 KB |
Output is correct |
10 |
Incorrect |
0 ms |
2728 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |