Submission #660803

#	Time	Username	Problem	Language	Result	Execution time	Memory
660803		danikoynov	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	52 ms	95196 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;
const ll inf = 1e18;

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

struct edge
{
    int u, p;
    ll w;

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

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

vector < edge > g[2010][2010];

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

    deque < edge > dq;
    dq.push_back(edge(d[0].b, d[0].p, 0));
    while(!dq.empty())
    {
        edge cur = dq.front();
        dq.pop_front();
        if (used[cur.u][cur.p] != -1)
            continue;
            used[cur.u][cur.p] = cur.w;
            ///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];
            if (used[nb.u][nb.p] != -1)
                continue;
            if (nb.w == 0)
            {
                dq.push_front(edge(nb.u, nb.p, cur.w));
            }
            else
            {
                dq.push_back(edge(nb.u, nb.p, cur.w + 1));
            }
        }
    }
}
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 < n; j ++)
        {
            if (i - j >= 0)
                g[i][j].push_back(edge(i - j, j, 1));
            if (i + j < n)
                g[i][j].push_back(edge(i + j, j, 1));
            g[i][j].push_back(edge(i, n, 0));
        }

    for (int i = 0; i < m; i ++)
    {
        g[d[i].b][n].push_back(edge(d[i].b, d[i].p, 0));
    }

    dijkstra(0);

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

int main()
{
    solve();
    return 0;
}
/**
7 2
0 10
3 2
*/

Compilation message (stderr)

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

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