#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
const int inf = int(1e9)+5, maxn = int(3e4)+5;
int D[maxn][2];
vector<pair<int, int>> A;
vector<int> graph[maxn];
set<pair<int, int>> doge[maxn];
// 0 => doge
// 1 => skyscraper
bool go(int x, int y)
{
if(A[x].first == y) return 1;
auto it = doge[y].lower_bound({A[x].second, -1});
return (it == doge[y].end() && it->first != A[x].second);
}
int main(void)
{
int n, m;
scanf("%d%d", &n, &m);
A.clear(); A.resize(m);
for(int i = 0;i < m;i++) scanf("%d%d", &A[i].first, &A[i].second), D[i][0] = inf;
for(int i = 0;i < n;i++) D[i][1] = inf;
sort(A.begin(), A.end());
A.resize(int(unique(A.begin(), A.end())-A.begin()));
m = int(A.size());
for(int i = 0;i < m;i++)
{
doge[A[i].first].insert({A[i].second, i});
}
for(int i = 0;i < m;i++)
{
for(int j = A[i].first;j < n;j += A[i].second)
{
if(go(i, j)) graph[i].push_back(j);
else
{
graph[i].push_back(j);
break;
}
}
for(int j = A[i].first;j >= 0;j -= A[i].second)
{
if(go(i, j)) graph[i].push_back(j);
else
{
graph[i].push_back(j);
break;
}
}
}
set<pair<int, pair<int, int>>> Q;
Q.insert({0, {0, 0}});
D[0][0] = 0;
while(!Q.empty())
{
pair<int, pair<int, int>> top = *Q.begin();
Q.erase(Q.begin());
//cout << top.first << " " << top.second.first << " " << top.second.second << "\n";
if(top.second.second)
{
for(auto it: doge[top.second.first])
{
if(D[it.second][0] > top.first)
{
if(D[it.second][0] != inf) Q.erase({D[it.second][0], {it.second, 0}});
D[it.second][0] = top.first;
Q.insert({D[it.second][0], {it.second, 0}});
}
}
}
else
{
for(auto it: graph[top.second.first])
{
int c = top.first+abs(it-A[top.second.first].first)/A[top.second.first].second;
if(D[it][1] > c)
{
if(D[it][1] != inf) Q.erase({D[it][1], {it, 1}});
D[it][1] = c;
Q.insert({D[it][1], {it, 1}});
}
}
}
}
printf("%d\n", (D[1][0] == inf)?-1:D[1][0]);
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
skyscraper.cpp:31:85: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0;i < m;i++) scanf("%d%d", &A[i].first, &A[i].second), D[i][0] = inf;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4372 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4372 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4372 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4372 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4372 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
