Submission #504065

#	Time	Username	Problem	Language	Result	Execution time	Memory
504065		FronPaw	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	267 ms	63100 KiB

skyscraper

#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);
      |     ~~~^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43