| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 238134 | HellAngel | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 0 ms | 0 KiB |
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>
using namespace std;
const int maxn = 50007;
int n, m, a[maxn], start[maxn], len[maxn], dist[maxn];
vector<int> pos[maxn];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
bool Inside(int x)
{
return (x >= 0 && x < n);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
cin >> n >> m;
fill_n(dist, n, 1e9);
for(int i = 1; i <= m; i++)
{
cin >> start[i] >> len[i];
pos[start[i]].push_back(len[i]);
}
for(int i = 0; i < n; i++)
{
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
reverse(pos[i].begin(), pos[i],end());
}
if(m == 1)
{
cout << -1;
return 0;
}
dist[start[1]] = 0;
pq.emplace(0, start[1]);
while(pq.size())
{
pair<int, int> p = pq.top();
pq.pop();
if(p.first != dist[p.second]) continue;
int u = p.second;
if(u == start[2])
{
cout << p.first;
exit(0);
}
for(auto j: pos[u])
{
int cnt = 0;
for(int i = 1;;i++)
{
int nxt = u + i * j;
bool ok = 0;
bool sure = 0;
ok |= Inside(nxt);
if(Inside(nxt) && dist[nxt] > dist[u] + i)
{
sure = 1;
dist[nxt] = dist[u] + i;
pq.emplace(dist[nxt], nxt);
}
nxt = u - i * j;
ok |= Inside(nxt);
if(Inside(nxt) && dist[nxt] > dist[u] + i)
{
sure = 1;
dist[nxt] = dist[u] + i;
pq.emplace(dist[nxt], nxt);
}
if(!sure)
{
cnt++;
}
else cnt = 0;
if(cnt >= 10000) break;
if(!ok) break;
}
}
}
cout << -1;
}