#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <map>
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<int, int> dp[1 + nmax];
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[node][jump2] == 0){
dp[node][jump2] = cost;
q.push({node, jump2});
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
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], 1);
while(0 < q.size()){
int node = q.front().first;
int jump = q.front().second;
int cost = dp[node][jump];
if(node == v[1][0]){
cout << cost;
return 0;
}
q.pop();
if(0 <= node - jump)
if(dp[node - jump][jump] == 0) {
dp[node - jump][jump] = cost + 1;
processlevel(node - jump, cost + 1);
q.push({node - jump, jump});
}
if(node + jump < n)
if(dp[node + jump][jump] == 0) {
dp[node + jump][jump] = cost + 1;
processlevel(node + jump, cost + 1);
q.push({node + jump, jump});
}
}
cout << dp[v[1][0]][v[1][1]] - 1;
return 0;
}
Compilation message
skyscraper.cpp: In function 'void processlevel(int, int)':
skyscraper.cpp:28: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 |
Incorrect |
6 ms |
2432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2432 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |