oj.uz

Submission #709880

# Submission time Handle Problem Language Result Execution time Memory
709880 2023-03-14T18:32:34 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 257564 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

const int INF = 1e9;
const int B = 70;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

int dist[MAXN][B];
vector<array<int, 3> > g[MAXN][B];

signed main()
{
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    d.resize(m);
    vector<int> big;
    for (int i = 0; i < m; i++)
    {
        cin >> d[i].first >> d[i].second;
        if (d[i].second >= B)
        {
            big.push_back(i);
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < B; j++)
            dist[i][j] = INF;
    for (int i = 0; i < m; i++)
    {
        if (d[i].second >= B) continue;
        g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < B; j++)
        {
            if (i - j >= 0)
            {
                g[i][j].push_back({i - j, 0, 1});
                g[i][j].push_back({i - j, j, 1});
            }
            if (i + j < n)
            {
                g[i][j].push_back({i + j, 0, 1});
                g[i][j].push_back({i + j, j, 1});
            }
        }
    }
    for (auto& i : big)
    {
        for (int j = d[i].first, k = 0; j < n; j += d[i].second, k++)
        {
            g[d[i].first][0].push_back({j, 0, k});
        }
        for (int j = d[i].first, k = 0; j >= 0; j -= d[i].second,  k++)
        {
            g[d[i].first][0].push_back({j, 0, k});
        }
    }
    set<array<int, 3> > st;
    st.insert({0, d[0].first, 0});
    dist[d[0].first][0] = 0;
    while (!st.empty())
    {
        auto [dst, pos, pw] = *st.begin();
        st.erase(st.begin());
        if (dst > dist[pos][pw]) continue;
        for (auto& [psu, pwu, w] : g[pos][pw])
        {
            if (dist[psu][pwu] > dst + w)
            {
                st.erase({dist[psu][pwu], psu, pwu});
                dist[psu][pwu] = dst + w;
                st.insert({dist[psu][pwu], psu, pwu});
            }
        }
    }
    int mn = INF;
    for (int i = 0; i < B; i++)
        mn = min(mn, dist[d[1].first][i]);
    if (mn == INF)
        cout << -1;
    else
        cout << mn;
    return 0;
}
/*
small
(i, j) -1> (i - j, 0), (i + j, 0)
(i, 0) -0> (i, j)
(i, j) -1> (i - j, j), (i + j, j)
large
(i, 0) -1> (i + j, 0)
(i, 0) -1> (i - j, 0)
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49560 KB Output is correct
2 Correct 26 ms 49536 KB Output is correct
3 Correct 26 ms 49548 KB Output is correct
4 Correct 25 ms 49628 KB Output is correct
5 Correct 25 ms 49584 KB Output is correct
6 Correct 25 ms 49620 KB Output is correct
7 Correct 24 ms 49656 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49528 KB Output is correct
2 Correct 32 ms 49632 KB Output is correct
3 Correct 30 ms 49612 KB Output is correct
4 Correct 31 ms 49620 KB Output is correct
5 Correct 24 ms 49620 KB Output is correct
6 Correct 24 ms 49552 KB Output is correct
7 Correct 26 ms 49652 KB Output is correct
8 Correct 32 ms 49644 KB Output is correct
9 Correct 26 ms 49748 KB Output is correct
10 Correct 27 ms 49876 KB Output is correct
11 Correct 27 ms 50004 KB Output is correct
12 Correct 31 ms 49872 KB Output is correct
13 Correct 27 ms 50004 KB Output is correct
14 Correct 34 ms 50092 KB Output is correct
15 Correct 29 ms 50132 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 49596 KB Output is correct
2 Correct 23 ms 49652 KB Output is correct
3 Correct 22 ms 49620 KB Output is correct
4 Correct 24 ms 49568 KB Output is correct
5 Correct 24 ms 49560 KB Output is correct
6 Correct 26 ms 49620 KB Output is correct
7 Correct 26 ms 49652 KB Output is correct
8 Correct 26 ms 49648 KB Output is correct
9 Correct 25 ms 49768 KB Output is correct
10 Correct 25 ms 49912 KB Output is correct
11 Correct 26 ms 50088 KB Output is correct
12 Correct 32 ms 49896 KB Output is correct
13 Correct 35 ms 49868 KB Output is correct
14 Correct 30 ms 50136 KB Output is correct
15 Correct 31 ms 50120 KB Output is correct
16 Correct 30 ms 50448 KB Output is correct
17 Correct 39 ms 53084 KB Output is correct
18 Correct 45 ms 57516 KB Output is correct
19 Correct 42 ms 58748 KB Output is correct
20 Correct 43 ms 58700 KB Output is correct
21 Correct 31 ms 51284 KB Output is correct
22 Correct 41 ms 57660 KB Output is correct
23 Correct 47 ms 56924 KB Output is correct
24 Correct 56 ms 58460 KB Output is correct
25 Correct 45 ms 58820 KB Output is correct
26 Correct 45 ms 58700 KB Output is correct
27 Correct 47 ms 58736 KB Output is correct
28 Correct 49 ms 58884 KB Output is correct
29 Correct 59 ms 58756 KB Output is correct
30 Correct 50 ms 58596 KB Output is correct
31 Correct 51 ms 58700 KB Output is correct
32 Correct 50 ms 58696 KB Output is correct
33 Correct 73 ms 58864 KB Output is correct
34 Correct 77 ms 58852 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49752 KB Output is correct
2 Correct 32 ms 49628 KB Output is correct
3 Correct 26 ms 49628 KB Output is correct
4 Correct 28 ms 49612 KB Output is correct
5 Correct 26 ms 49584 KB Output is correct
6 Correct 26 ms 49620 KB Output is correct
7 Correct 26 ms 49720 KB Output is correct
8 Correct 26 ms 49632 KB Output is correct
9 Correct 26 ms 49700 KB Output is correct
10 Correct 27 ms 49876 KB Output is correct
11 Correct 28 ms 49968 KB Output is correct
12 Correct 26 ms 49996 KB Output is correct
13 Correct 27 ms 49892 KB Output is correct
14 Correct 27 ms 50020 KB Output is correct
15 Correct 28 ms 50032 KB Output is correct
16 Correct 29 ms 50388 KB Output is correct
17 Correct 36 ms 53112 KB Output is correct
18 Correct 42 ms 57588 KB Output is correct
19 Correct 47 ms 58644 KB Output is correct
20 Correct 43 ms 58700 KB Output is correct
21 Correct 30 ms 51308 KB Output is correct
22 Correct 41 ms 57652 KB Output is correct
23 Correct 42 ms 56904 KB Output is correct
24 Correct 48 ms 58428 KB Output is correct
25 Correct 47 ms 58816 KB Output is correct
26 Correct 51 ms 58688 KB Output is correct
27 Correct 46 ms 58700 KB Output is correct
28 Correct 48 ms 58864 KB Output is correct
29 Correct 58 ms 58760 KB Output is correct
30 Correct 47 ms 58680 KB Output is correct
31 Correct 51 ms 58636 KB Output is correct
32 Correct 54 ms 58736 KB Output is correct
33 Correct 77 ms 58908 KB Output is correct
34 Correct 72 ms 58856 KB Output is correct
35 Correct 59 ms 58328 KB Output is correct
36 Correct 40 ms 54908 KB Output is correct
37 Correct 95 ms 61132 KB Output is correct
38 Correct 78 ms 61684 KB Output is correct
39 Correct 81 ms 61748 KB Output is correct
40 Correct 74 ms 61688 KB Output is correct
41 Correct 78 ms 61812 KB Output is correct
42 Correct 49 ms 59356 KB Output is correct
43 Correct 48 ms 59372 KB Output is correct
44 Correct 50 ms 59372 KB Output is correct
45 Correct 91 ms 65540 KB Output is correct
46 Correct 98 ms 65532 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49584 KB Output is correct
2 Correct 31 ms 49604 KB Output is correct
3 Correct 29 ms 49528 KB Output is correct
4 Correct 30 ms 49536 KB Output is correct
5 Correct 27 ms 49620 KB Output is correct
6 Correct 27 ms 49760 KB Output is correct
7 Correct 27 ms 49612 KB Output is correct
8 Correct 31 ms 49652 KB Output is correct
9 Correct 32 ms 49688 KB Output is correct
10 Correct 33 ms 49988 KB Output is correct
11 Correct 28 ms 50088 KB Output is correct
12 Correct 28 ms 49892 KB Output is correct
13 Correct 27 ms 49896 KB Output is correct
14 Correct 29 ms 50040 KB Output is correct
15 Correct 33 ms 50132 KB Output is correct
16 Correct 29 ms 50328 KB Output is correct
17 Correct 41 ms 53068 KB Output is correct
18 Correct 49 ms 57564 KB Output is correct
19 Correct 46 ms 58700 KB Output is correct
20 Correct 44 ms 58672 KB Output is correct
21 Correct 30 ms 51276 KB Output is correct
22 Correct 41 ms 57660 KB Output is correct
23 Correct 44 ms 56908 KB Output is correct
24 Correct 49 ms 58440 KB Output is correct
25 Correct 49 ms 58800 KB Output is correct
26 Correct 44 ms 58740 KB Output is correct
27 Correct 46 ms 58732 KB Output is correct
28 Correct 56 ms 58828 KB Output is correct
29 Correct 59 ms 58752 KB Output is correct
30 Correct 47 ms 58664 KB Output is correct
31 Correct 53 ms 58668 KB Output is correct
32 Correct 49 ms 58644 KB Output is correct
33 Correct 83 ms 58864 KB Output is correct
34 Correct 86 ms 58860 KB Output is correct
35 Correct 76 ms 58336 KB Output is correct
36 Correct 39 ms 54860 KB Output is correct
37 Correct 75 ms 61076 KB Output is correct
38 Correct 75 ms 61720 KB Output is correct
39 Correct 75 ms 61708 KB Output is correct
40 Correct 75 ms 61640 KB Output is correct
41 Correct 75 ms 61772 KB Output is correct
42 Correct 46 ms 59380 KB Output is correct
43 Correct 56 ms 59340 KB Output is correct
44 Correct 71 ms 59492 KB Output is correct
45 Correct 98 ms 65596 KB Output is correct
46 Correct 96 ms 65660 KB Output is correct
47 Correct 320 ms 115444 KB Output is correct
48 Correct 284 ms 159228 KB Output is correct
49 Correct 273 ms 168792 KB Output is correct
50 Correct 313 ms 179816 KB Output is correct
51 Correct 417 ms 192652 KB Output is correct
52 Correct 435 ms 192832 KB Output is correct
53 Correct 375 ms 189088 KB Output is correct
54 Correct 317 ms 187324 KB Output is correct
55 Correct 331 ms 187312 KB Output is correct
56 Correct 338 ms 188636 KB Output is correct
57 Correct 580 ms 187492 KB Output is correct
58 Correct 339 ms 187964 KB Output is correct
59 Correct 396 ms 188148 KB Output is correct
60 Correct 403 ms 188988 KB Output is correct
61 Correct 439 ms 188644 KB Output is correct
62 Correct 448 ms 193176 KB Output is correct
63 Correct 490 ms 222940 KB Output is correct
64 Correct 611 ms 236004 KB Output is correct
65 Correct 636 ms 245048 KB Output is correct
66 Execution timed out 1054 ms 257564 KB Time limit exceeded
67 Halted 0 ms 0 KB -