Submission #411697

#	Time	Username	Problem	Language	Result	Execution time	Memory
411697		MasterTaster	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	1728 KiB

skyscraper

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define INF 1000000010LL
#define MAXN 30010

using namespace std;

ll d[MAXN];
int n, m;
vector<int> g[MAXN];
vector<ll> w[MAXN];

void dijkstra(int s)
{
    for (int i=0; i<n; i++) d[i]=INF;
    d[s]=0;

    set< pair<int, ll> > q;
    q.insert({0, s});

    while (!q.empty())
    {
        int u=q.begin()->second;
        q.erase(q.begin());

        for (int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if (d[u]+w[u][i]<d[v])
            {
                q.erase({d[v], v});

                d[v]=d[u]+w[u][i];
                q.insert({d[v], v});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>m;

    for (int i=0; i<m; i++)
    {
        int u; cin>>u;
        int p; cin>>p;

        for (int j=1; u-j*p>=0; j++) { g[u].pb(u-j*p); w[u].pb(j); }
        for (int j=1; u+j*p<n; j++) { g[u].pb(u+j*p); w[u].pb(j); }
    }

    dijkstra(0);
    if (d[1]==INF) cout<<-1;
    else cout<<d[1];
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra(int)':
skyscraper.cpp:31:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int i=0; i<g[u].size(); i++)
      |                       ~^~~~~~~~~~~~

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