#include<bits/stdc++.h>
using namespace std;
const int nax = 3e4 + 3;
const int INF = 1e9;
int b[nax], p[nax];
vector<int>doges[nax];
unordered_map<long long,int>dist;
int get(int x, int y) {
long long H = x * 10000000LL + y;
if(dist.find(H)!=dist.end()) return dist[H];
return INF;
}
void put(int x, int y, int val) {
long long H = x * 10000000LL + y;
dist[H] = val;
}
void PlayGround() {
int n, m;
cin>>n>>m;
for(int i=0; i<m; ++i) {
cin>>b[i]>>p[i];
doges[b[i]].push_back(p[i]);
}
put(b[0], 0, 0);
queue<tuple<int,int,int>>q;
q.push({b[0], 0, 0});
int lim = n * 15;
while(!q.empty()) {
assert(dist.size()<lim);
auto x = q.front();
q.pop();
int ss, j, d;
tie(ss, j, d) = x;
if(d!=get(ss, j)) continue;
if(j==0) {
for(int z : doges[ss]) {
if(get(ss, z)>d) {
put(ss, z, d);
q.emplace(ss, z, d);
}
}
} else {
if(ss+j<n) {
if(get(ss+j, j)>d+1) {
put(ss+j, j, d+1);
q.emplace(ss+j, j, d+1);
}
if(get(ss+j, 0)>d+1) {
put(ss+j, 0, d+1);
q.emplace(ss+j, 0, d+1);
}
}
if(ss-j>=0) {
if(get(ss-j, j)>d+1) {
put(ss-j, j, d+1);
q.emplace(ss-j, j, d+1);
}
if(get(ss-j, 0)>d+1) {
put(ss-j, 0, d+1);
q.emplace(ss-j, 0, d+1);
}
}
}
}
int ans = get(b[1], 0);
if(ans==INF) ans = -1;
cout<<ans<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from skyscraper.cpp:1:
skyscraper.cpp: In function 'void PlayGround()':
skyscraper.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
38 | assert(dist.size()<lim);
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Runtime error |
2 ms |
2020 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Runtime error |
2 ms |
2004 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |