This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define mod 1000000007
// https://www.youtube.com/watch?v=t5GDacP_2pQ
using namespace std;
ifstream in ("film.in");
ofstream out ("film.out");
int pow (int a, int b)
{
int rez = 1;
while (b)
{
if (b&1)
rez = (rez * a) % mod;
a = (a * a) % mod;
b>>=1;
}
return rez;
}
int n, m;
set <int> b[30001];
vector <pair <int, int> > v[30001];
int ans[30001];
void dij (int start)
{
for (int i = 0; i<=30000; ++i)
ans[i] = 1<<30;
ans[start] = 0;
set <pair<int, int> > q;
q.insert({0, start});
while (!q.empty())
{
int nod = (*q.begin()).second;
q.erase(q.begin());
int cost = ans[nod];
for (auto vecin:v[nod])
if (cost + vecin.second < ans[vecin.first])
{
if (ans[vecin.first] != 1<<30)
q.erase(q.find({ans[vecin.first], vecin.first}));
q.insert({cost + vecin.second, vecin.first});
ans[vecin.first] = cost + vecin.second;
}
}
}
void solve ()
{
int first, last;
cin >> n >> m;
for (int i = 1; i<=m; ++i)
{
int a, c;
cin >> a >> c;
if (i == 1)
first = a;
else if (i == 2)
last = a;
b[a].insert(c);
}
for (int i = 0; i<n; ++i)
for (auto pp:b[i])
{
int place = i;
place -= pp;
int move1 = 1;
while (place >= 0)
{
v[i].push_back({place, move1});
if (b[place].count(pp))
break;
move1++;
place -= pp;
}
place = i + pp;
move1 = 1;
while (place < n)
{
v[i].push_back({place, move1});
if (b[place].count(pp))
break;
move1++;
place += pp;
}
}
dij(first);
if (ans[last] == 1<<30)
cout << -1 << ' ';
else
cout << ans[last] << ' ';
return;
}
main ()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int t = 1;
//cin >> t;
while (t--)
solve();
}
Compilation message (stderr)
skyscraper.cpp:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
92 | main ()
| ^~~~
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:86:17: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
86 | if (ans[last] == 1<<30)
| ~~~~~~~~^
skyscraper.cpp:85:8: warning: 'first' may be used uninitialized in this function [-Wmaybe-uninitialized]
85 | dij(first);
| ~~~^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |