Submission #660863

#	Time	Username	Problem	Language	Result	Execution time	Memory
660863		danikoynov	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	930 ms	228728 KiB

skyscraper

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 30010, block = 50;
const ll inf = 1e9;

struct doge
{
    int b, p;
} d[maxn];

struct edge
{
    int u, p;
    int w;

    edge(int _u, int _p, int _w)
    {
        p = _p;
        u = _u;
        w = _w;
    }

    bool operator < (const edge &e) const
    {
        return w > e.w;
    }
};

vector < edge > g[maxn][block + 10];

int n, m, used[maxn][block + 10];
int dp[maxn][block + 10];
void dijkstra(int s)
{
    for (int i = 0; i <= n; i ++)
    for (int j = 0; j <= block; j ++)
    {
        used[i][j] = -1;
        dp[i][j] = 1e9;
    }

    priority_queue < edge > pq;
    pq.push(edge(d[0].b, block, 0));
    while(!pq.empty())
    {
        edge cur = pq.top();
        ///---------------
        pq.pop();

        if (used[cur.u][cur.p] != -1)
            continue;
            used[cur.u][cur.p] = 1;
            ///cout << cur.u << " : " << cur.p << " " << cur.w << endl;
        for (int i = 0; i < g[cur.u][cur.p].size(); i ++)
        {
            edge nb = g[cur.u][cur.p][i];
            ///cout << "neib " << nb.u << " -- " << nb.w << endl;
            nb.w += cur.w;
            if (dp[nb.u][nb.p] > nb.w)
            {
                dp[nb.u][nb.p] = nb.w;
                pq.push(nb);
            }
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        cin >> d[i].b >> d[i].p;
    }


    for (int i = 0; i < n; i ++)
        for (int j = 1; j < block; j ++)
        {
            if (i - j >= 0)
            {
                g[i][j].push_back(edge(i - j, j, 1));
                g[i][j].push_back(edge(i - j, block, 1));
            }
            if (i + j < n)
            {
                g[i][j].push_back(edge(i + j, block, 1));
                g[i][j].push_back(edge(i + j, j, 1));
            }
        }


    for (int i = 0; i < m; i ++)
    {
        if (d[i].p < block)
            g[d[i].b][block].push_back(edge(d[i].b, d[i].p, 0));
        if (d[i].p >= block)
        {
            for (int j = 1; d[i].b - d[i].p * j >= 0; j ++)
            {
                g[d[i].b][block].push_back(edge(d[i].b - d[i].p * j, block, j));
            }
            for (int j = 1; d[i].b + d[i].p * j < n; j ++)
            {
                g[d[i].b][block].push_back(edge(d[i].b + d[i].p * j, block, j));
            }
        }
    }

    dijkstra(0);

    ll best = inf;
    for (int j = 0; j <= block; j ++)
    {
        if (used[d[1].b][j] != -1)
            best = min(best, (ll)dp[d[1].b][j]);
    }
    if (best == inf)
        cout << -1 << endl;
    else
        cout << best << endl;
}

int main()
{
    solve();
    return 0;
}
/**
8 3
3 2
4 6
7 3
*/

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra(int)':
skyscraper.cpp:61:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |         if (used[cur.u][cur.p] != -1)
      |         ^~
skyscraper.cpp:63:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |             used[cur.u][cur.p] = 1;
      |             ^~~~
skyscraper.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < g[cur.u][cur.p].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~

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