#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 30000;
int v[1 + nmax][2];
vector<int> g[1 + nmax];
map<pair<int,int>, int> dp;
int seen[1 + nmax];
queue<pair<int,int>> q;
void processlevel(int node, int cost){
if(seen[node] == 1)
return ;
seen[node] = 1;
for(int h = 0; h < g[node].size(); h++){
int jump2 = g[node][h];
if(dp.find({node, jump2}) == dp.end()){
dp[{node, jump2}] = cost;
q.push({node, jump2});
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0;i < m; i++) {
cin >> v[i][0] >> v[i][1];
g[v[i][0]].push_back(v[i][1]);
}
processlevel(v[0][0], 0);
while(0 < q.size()){
int node = q.front().first;
int jump = q.front().second;
int cost = dp[{node, jump}];
q.pop();
if(0 <= node - jump)
if(dp.find({node - jump, jump}) == dp.end()) {
dp[{node - jump, jump}] = cost + 1;
processlevel(node + jump, cost + 1);
q.push({node - jump, jump});
}
if(node + jump < n)
if(dp.find({node + jump, jump}) == dp.end()) {
dp[{node + jump, jump}] = cost + 1;
processlevel(node + jump, cost + 1);
q.push({node + jump, jump});
}
}
if(dp.find({v[1][0], v[1][1]}) == dp.end())
cout << -1;
else
cout << dp[{v[1][0], v[1][1]}];
return 0;
}
Compilation message
skyscraper.cpp: In function 'void processlevel(int, int)':
skyscraper.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1024 KB |
Output is correct |
2 |
Correct |
5 ms |
1024 KB |
Output is correct |
3 |
Correct |
5 ms |
1024 KB |
Output is correct |
4 |
Correct |
5 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
1024 KB |
Output is correct |
6 |
Incorrect |
5 ms |
1024 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1024 KB |
Output is correct |
2 |
Correct |
5 ms |
1024 KB |
Output is correct |
3 |
Correct |
5 ms |
1024 KB |
Output is correct |
4 |
Correct |
5 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
1024 KB |
Output is correct |
6 |
Incorrect |
5 ms |
1024 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1024 KB |
Output is correct |
2 |
Correct |
5 ms |
1024 KB |
Output is correct |
3 |
Correct |
5 ms |
1024 KB |
Output is correct |
4 |
Correct |
5 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
1024 KB |
Output is correct |
6 |
Incorrect |
5 ms |
1024 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1024 KB |
Output is correct |
2 |
Correct |
5 ms |
1024 KB |
Output is correct |
3 |
Correct |
5 ms |
1024 KB |
Output is correct |
4 |
Correct |
5 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
1024 KB |
Output is correct |
6 |
Incorrect |
5 ms |
1024 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1024 KB |
Output is correct |
2 |
Correct |
5 ms |
1024 KB |
Output is correct |
3 |
Correct |
5 ms |
1024 KB |
Output is correct |
4 |
Correct |
5 ms |
1024 KB |
Output is correct |
5 |
Correct |
5 ms |
1024 KB |
Output is correct |
6 |
Incorrect |
5 ms |
1024 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |