oj.uz

Submission #660863

# Submission time Handle Problem Language Result Execution time Memory
660863 2022-11-23T10:59:13 Z danikoynov Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 930 ms 228728 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42580 KB Output is correct
2 Correct 22 ms 42580 KB Output is correct
3 Correct 20 ms 42492 KB Output is correct
4 Correct 20 ms 42520 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 21 ms 42512 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42608 KB Output is correct
2 Correct 21 ms 42580 KB Output is correct
3 Correct 21 ms 42512 KB Output is correct
4 Correct 21 ms 42580 KB Output is correct
5 Correct 22 ms 42580 KB Output is correct
6 Correct 21 ms 42528 KB Output is correct
7 Correct 22 ms 42592 KB Output is correct
8 Correct 21 ms 42644 KB Output is correct
9 Correct 21 ms 42732 KB Output is correct
10 Correct 22 ms 42776 KB Output is correct
11 Correct 23 ms 42956 KB Output is correct
12 Correct 25 ms 42928 KB Output is correct
13 Correct 24 ms 42836 KB Output is correct
14 Correct 22 ms 42964 KB Output is correct
15 Correct 22 ms 42872 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42580 KB Output is correct
2 Correct 21 ms 42596 KB Output is correct
3 Correct 21 ms 42544 KB Output is correct
4 Correct 21 ms 42612 KB Output is correct
5 Correct 22 ms 42580 KB Output is correct
6 Correct 22 ms 42580 KB Output is correct
7 Correct 22 ms 42580 KB Output is correct
8 Correct 25 ms 42552 KB Output is correct
9 Correct 26 ms 42616 KB Output is correct
10 Correct 23 ms 42828 KB Output is correct
11 Correct 22 ms 42836 KB Output is correct
12 Correct 22 ms 42928 KB Output is correct
13 Correct 23 ms 42904 KB Output is correct
14 Correct 24 ms 42976 KB Output is correct
15 Correct 24 ms 42932 KB Output is correct
16 Correct 23 ms 43220 KB Output is correct
17 Correct 28 ms 45236 KB Output is correct
18 Correct 33 ms 48664 KB Output is correct
19 Correct 34 ms 49620 KB Output is correct
20 Correct 37 ms 49580 KB Output is correct
21 Correct 25 ms 43928 KB Output is correct
22 Correct 37 ms 48804 KB Output is correct
23 Correct 33 ms 48224 KB Output is correct
24 Correct 37 ms 49356 KB Output is correct
25 Correct 35 ms 49620 KB Output is correct
26 Correct 37 ms 49676 KB Output is correct
27 Correct 35 ms 49540 KB Output is correct
28 Correct 36 ms 49728 KB Output is correct
29 Correct 42 ms 49624 KB Output is correct
30 Correct 37 ms 49612 KB Output is correct
31 Correct 39 ms 49608 KB Output is correct
32 Correct 37 ms 49592 KB Output is correct
33 Correct 48 ms 50288 KB Output is correct
34 Correct 49 ms 50392 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42532 KB Output is correct
2 Correct 20 ms 42576 KB Output is correct
3 Correct 21 ms 42580 KB Output is correct
4 Correct 20 ms 42580 KB Output is correct
5 Correct 21 ms 42572 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 20 ms 42580 KB Output is correct
8 Correct 21 ms 42556 KB Output is correct
9 Correct 22 ms 42708 KB Output is correct
10 Correct 21 ms 42836 KB Output is correct
11 Correct 23 ms 42928 KB Output is correct
12 Correct 23 ms 42928 KB Output is correct
13 Correct 22 ms 42896 KB Output is correct
14 Correct 22 ms 42952 KB Output is correct
15 Correct 23 ms 42908 KB Output is correct
16 Correct 22 ms 43256 KB Output is correct
17 Correct 28 ms 45180 KB Output is correct
18 Correct 35 ms 48724 KB Output is correct
19 Correct 33 ms 49620 KB Output is correct
20 Correct 37 ms 49632 KB Output is correct
21 Correct 24 ms 43848 KB Output is correct
22 Correct 33 ms 48724 KB Output is correct
23 Correct 32 ms 48208 KB Output is correct
24 Correct 34 ms 49364 KB Output is correct
25 Correct 35 ms 49640 KB Output is correct
26 Correct 35 ms 49704 KB Output is correct
27 Correct 35 ms 49612 KB Output is correct
28 Correct 37 ms 49724 KB Output is correct
29 Correct 42 ms 49612 KB Output is correct
30 Correct 38 ms 49488 KB Output is correct
31 Correct 43 ms 49596 KB Output is correct
32 Correct 36 ms 49620 KB Output is correct
33 Correct 50 ms 50336 KB Output is correct
34 Correct 51 ms 50372 KB Output is correct
35 Correct 50 ms 48636 KB Output is correct
36 Correct 38 ms 46504 KB Output is correct
37 Correct 60 ms 51572 KB Output is correct
38 Correct 59 ms 51440 KB Output is correct
39 Correct 60 ms 51456 KB Output is correct
40 Correct 61 ms 51508 KB Output is correct
41 Correct 82 ms 51472 KB Output is correct
42 Correct 45 ms 50252 KB Output is correct
43 Correct 45 ms 50260 KB Output is correct
44 Correct 45 ms 50232 KB Output is correct
45 Correct 65 ms 55724 KB Output is correct
46 Correct 68 ms 55640 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42608 KB Output is correct
2 Correct 21 ms 42604 KB Output is correct
3 Correct 26 ms 42592 KB Output is correct
4 Correct 21 ms 42580 KB Output is correct
5 Correct 21 ms 42580 KB Output is correct
6 Correct 20 ms 42552 KB Output is correct
7 Correct 20 ms 42560 KB Output is correct
8 Correct 21 ms 42664 KB Output is correct
9 Correct 21 ms 42708 KB Output is correct
10 Correct 23 ms 42768 KB Output is correct
11 Correct 27 ms 42900 KB Output is correct
12 Correct 21 ms 42948 KB Output is correct
13 Correct 21 ms 42940 KB Output is correct
14 Correct 22 ms 42892 KB Output is correct
15 Correct 24 ms 42964 KB Output is correct
16 Correct 29 ms 43212 KB Output is correct
17 Correct 31 ms 45220 KB Output is correct
18 Correct 37 ms 48628 KB Output is correct
19 Correct 37 ms 49580 KB Output is correct
20 Correct 39 ms 49636 KB Output is correct
21 Correct 28 ms 43868 KB Output is correct
22 Correct 36 ms 48780 KB Output is correct
23 Correct 35 ms 48100 KB Output is correct
24 Correct 42 ms 49296 KB Output is correct
25 Correct 36 ms 49580 KB Output is correct
26 Correct 39 ms 49616 KB Output is correct
27 Correct 36 ms 49568 KB Output is correct
28 Correct 43 ms 49724 KB Output is correct
29 Correct 47 ms 49628 KB Output is correct
30 Correct 43 ms 49496 KB Output is correct
31 Correct 43 ms 49592 KB Output is correct
32 Correct 42 ms 49664 KB Output is correct
33 Correct 56 ms 50232 KB Output is correct
34 Correct 53 ms 50360 KB Output is correct
35 Correct 57 ms 48732 KB Output is correct
36 Correct 33 ms 46464 KB Output is correct
37 Correct 59 ms 51572 KB Output is correct
38 Correct 64 ms 51388 KB Output is correct
39 Correct 63 ms 51444 KB Output is correct
40 Correct 74 ms 51472 KB Output is correct
41 Correct 73 ms 51540 KB Output is correct
42 Correct 47 ms 50252 KB Output is correct
43 Correct 55 ms 50264 KB Output is correct
44 Correct 51 ms 50300 KB Output is correct
45 Correct 72 ms 55804 KB Output is correct
46 Correct 77 ms 55556 KB Output is correct
47 Correct 262 ms 94916 KB Output is correct
48 Correct 197 ms 126788 KB Output is correct
49 Correct 211 ms 134040 KB Output is correct
50 Correct 224 ms 142624 KB Output is correct
51 Correct 317 ms 152136 KB Output is correct
52 Correct 318 ms 152368 KB Output is correct
53 Correct 250 ms 148876 KB Output is correct
54 Correct 217 ms 148600 KB Output is correct
55 Correct 223 ms 148580 KB Output is correct
56 Correct 245 ms 149724 KB Output is correct
57 Correct 398 ms 150320 KB Output is correct
58 Correct 270 ms 149364 KB Output is correct
59 Correct 262 ms 149400 KB Output is correct
60 Correct 276 ms 150344 KB Output is correct
61 Correct 282 ms 149700 KB Output is correct
62 Correct 290 ms 153428 KB Output is correct
63 Correct 323 ms 184956 KB Output is correct
64 Correct 365 ms 198164 KB Output is correct
65 Correct 418 ms 205940 KB Output is correct
66 Correct 930 ms 228728 KB Output is correct
67 Correct 870 ms 227016 KB Output is correct