Submission #504049

#	Time	Username	Problem	Language	Result	Execution time	Memory
504049		FronPaw	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	112 ms	34128 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;
int b[30001], p[30001];
vector <pair <int, int> > v[30001];
int ans[30001];
void dij (int start)
{
    for (int i = 1;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;
        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;
            }
        q.erase(q.begin());
    }

}
void solve ()
{
    cin >> n >> m;
    for (int i = 1; i<=m; ++i)
        cin >> b[i] >> p[i];
    for (int i = 1; i<=m; ++i)
    {
        int place = b[i];
        int cat = p[i];
        place -= cat;
        int move1 = 1;
        while (place >= 0)
        {
            v[b[i]].push_back({place, move1});
            move1++;
            place -= cat;
        }
        place = b[i] + cat;
        move1 = 1;
        while (place < n)
        {
            v[b[i]].push_back({place, move1});
            move1++;
            place += cat;
        }
    }
    dij(b[1]);
    if (ans[b[2]] == 1<<30)
        cout << -1 << ' ';
    else
        cout << ans[b[2]] << ' ';
    return;
}
main ()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

skyscraper.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main ()
      | ^~~~

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