#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[21000005];
int dist[21000005], a[30005][175];
deque<int> deq;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, s, t, sz;
cin >> n >> m;
sz=n;
for (int i=0; i<m; i++)
{
int b, p;
cin >> b >> p;
if (i==0)
s=b;
else if (i==1)
t=b;
if (p*p<=m)
{
if (!a[b][p])
{
a[b%p][p]=sz;
sz++;
adj[a[b%p][p]].push_back({b%p, 0});
for (int j=b%p+p; j<n; j+=p)
{
a[j][p]=sz;
sz++;
adj[a[j][p]].push_back({j, 0});
adj[a[j][p]].push_back({a[j-p][p], 1});
adj[a[j-p][p]].push_back({a[j][p], 1});
}
}
adj[b].push_back({a[b][p], 0});
}
else
{
int prev=b;
for (int j=b-p; j>=0; j-=p)
{
adj[prev].push_back({sz, 1});
adj[sz].push_back({j, 0});
prev=sz;
sz++;
}
prev=b;
for (int j=b+p; j<n; j+=p)
{
adj[prev].push_back({sz, 1});
adj[sz].push_back({j, 0});
prev=sz;
sz++;
}
}
}
for (int i=0; i<sz; i++)
dist[i]=1e9;
dist[s]=0;
deq.push_back(s);
while (!deq.empty())
{
int u=deq.front();
deq.pop_front();
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second;
if (dist[v]==1e9)
{
dist[v]=dist[u]+w;
if (w)
deq.push_back(v);
else
deq.push_front(v);
}
}
}
if (dist[t]==1e9)
cout << -1;
else
cout << dist[t];
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i=0; i<adj[u].size(); i++)
| ~^~~~~~~~~~~~~~
skyscraper.cpp:81:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | if (dist[t]==1e9)
| ~~~~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
123 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
98 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
119 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
118 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
104 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |