oj.uz

Submission #709874

# Submission time Handle Problem Language Result Execution time Memory
709874 2023-03-14T18:29:23 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 454 ms 262144 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 = 100;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

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

int 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 33 ms 70716 KB Output is correct
2 Correct 37 ms 70724 KB Output is correct
3 Correct 35 ms 70720 KB Output is correct
4 Correct 32 ms 70772 KB Output is correct
5 Correct 35 ms 70708 KB Output is correct
6 Correct 33 ms 70792 KB Output is correct
7 Correct 34 ms 70712 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70680 KB Output is correct
2 Correct 35 ms 70680 KB Output is correct
3 Correct 34 ms 70792 KB Output is correct
4 Correct 35 ms 70732 KB Output is correct
5 Correct 36 ms 70740 KB Output is correct
6 Correct 41 ms 70768 KB Output is correct
7 Correct 35 ms 70684 KB Output is correct
8 Correct 34 ms 70732 KB Output is correct
9 Correct 34 ms 70844 KB Output is correct
10 Correct 35 ms 71152 KB Output is correct
11 Correct 37 ms 71200 KB Output is correct
12 Correct 34 ms 71100 KB Output is correct
13 Correct 36 ms 71132 KB Output is correct
14 Correct 36 ms 71252 KB Output is correct
15 Correct 36 ms 71244 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70652 KB Output is correct
2 Correct 34 ms 70852 KB Output is correct
3 Correct 35 ms 70684 KB Output is correct
4 Correct 36 ms 70656 KB Output is correct
5 Correct 36 ms 70772 KB Output is correct
6 Correct 33 ms 70772 KB Output is correct
7 Correct 35 ms 70720 KB Output is correct
8 Correct 40 ms 70824 KB Output is correct
9 Correct 40 ms 70904 KB Output is correct
10 Correct 41 ms 71076 KB Output is correct
11 Correct 43 ms 71212 KB Output is correct
12 Correct 43 ms 71124 KB Output is correct
13 Correct 40 ms 71164 KB Output is correct
14 Correct 40 ms 71192 KB Output is correct
15 Correct 41 ms 71176 KB Output is correct
16 Correct 40 ms 71740 KB Output is correct
17 Correct 51 ms 75532 KB Output is correct
18 Correct 64 ms 82080 KB Output is correct
19 Correct 67 ms 83592 KB Output is correct
20 Correct 57 ms 83600 KB Output is correct
21 Correct 39 ms 73004 KB Output is correct
22 Correct 54 ms 82172 KB Output is correct
23 Correct 53 ms 81012 KB Output is correct
24 Correct 59 ms 83064 KB Output is correct
25 Correct 58 ms 83716 KB Output is correct
26 Correct 66 ms 83712 KB Output is correct
27 Correct 59 ms 83624 KB Output is correct
28 Correct 60 ms 83724 KB Output is correct
29 Correct 72 ms 83652 KB Output is correct
30 Correct 59 ms 83620 KB Output is correct
31 Correct 64 ms 83680 KB Output is correct
32 Correct 63 ms 83664 KB Output is correct
33 Correct 98 ms 83780 KB Output is correct
34 Correct 88 ms 83820 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70764 KB Output is correct
2 Correct 34 ms 70768 KB Output is correct
3 Correct 33 ms 70668 KB Output is correct
4 Correct 35 ms 70700 KB Output is correct
5 Correct 36 ms 70708 KB Output is correct
6 Correct 33 ms 70712 KB Output is correct
7 Correct 35 ms 70752 KB Output is correct
8 Correct 36 ms 70868 KB Output is correct
9 Correct 34 ms 70840 KB Output is correct
10 Correct 35 ms 71116 KB Output is correct
11 Correct 35 ms 71156 KB Output is correct
12 Correct 34 ms 71168 KB Output is correct
13 Correct 37 ms 71164 KB Output is correct
14 Correct 39 ms 71288 KB Output is correct
15 Correct 35 ms 71244 KB Output is correct
16 Correct 35 ms 71704 KB Output is correct
17 Correct 45 ms 75428 KB Output is correct
18 Correct 56 ms 82000 KB Output is correct
19 Correct 57 ms 83696 KB Output is correct
20 Correct 59 ms 83720 KB Output is correct
21 Correct 38 ms 73108 KB Output is correct
22 Correct 55 ms 82156 KB Output is correct
23 Correct 55 ms 81044 KB Output is correct
24 Correct 61 ms 83108 KB Output is correct
25 Correct 62 ms 83760 KB Output is correct
26 Correct 59 ms 83716 KB Output is correct
27 Correct 60 ms 83848 KB Output is correct
28 Correct 59 ms 83820 KB Output is correct
29 Correct 73 ms 83664 KB Output is correct
30 Correct 60 ms 83656 KB Output is correct
31 Correct 65 ms 83656 KB Output is correct
32 Correct 64 ms 83572 KB Output is correct
33 Correct 91 ms 83728 KB Output is correct
34 Correct 88 ms 83824 KB Output is correct
35 Correct 76 ms 81932 KB Output is correct
36 Correct 50 ms 77908 KB Output is correct
37 Correct 101 ms 85528 KB Output is correct
38 Correct 94 ms 86384 KB Output is correct
39 Correct 106 ms 86392 KB Output is correct
40 Correct 112 ms 86380 KB Output is correct
41 Correct 94 ms 86348 KB Output is correct
42 Correct 63 ms 84176 KB Output is correct
43 Correct 62 ms 84248 KB Output is correct
44 Correct 61 ms 84188 KB Output is correct
45 Correct 117 ms 89356 KB Output is correct
46 Correct 116 ms 89420 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70672 KB Output is correct
2 Correct 34 ms 70672 KB Output is correct
3 Correct 35 ms 70740 KB Output is correct
4 Correct 34 ms 70700 KB Output is correct
5 Correct 34 ms 70740 KB Output is correct
6 Correct 34 ms 70688 KB Output is correct
7 Correct 37 ms 70708 KB Output is correct
8 Correct 36 ms 70780 KB Output is correct
9 Correct 35 ms 70852 KB Output is correct
10 Correct 37 ms 71116 KB Output is correct
11 Correct 37 ms 71232 KB Output is correct
12 Correct 37 ms 71048 KB Output is correct
13 Correct 36 ms 71124 KB Output is correct
14 Correct 39 ms 71300 KB Output is correct
15 Correct 37 ms 71208 KB Output is correct
16 Correct 37 ms 71804 KB Output is correct
17 Correct 46 ms 75476 KB Output is correct
18 Correct 56 ms 82052 KB Output is correct
19 Correct 58 ms 83620 KB Output is correct
20 Correct 59 ms 83676 KB Output is correct
21 Correct 44 ms 73028 KB Output is correct
22 Correct 55 ms 82136 KB Output is correct
23 Correct 64 ms 81076 KB Output is correct
24 Correct 63 ms 83176 KB Output is correct
25 Correct 57 ms 83676 KB Output is correct
26 Correct 64 ms 83616 KB Output is correct
27 Correct 60 ms 83728 KB Output is correct
28 Correct 60 ms 83816 KB Output is correct
29 Correct 75 ms 83712 KB Output is correct
30 Correct 63 ms 83532 KB Output is correct
31 Correct 65 ms 83700 KB Output is correct
32 Correct 66 ms 83684 KB Output is correct
33 Correct 88 ms 83824 KB Output is correct
34 Correct 88 ms 83720 KB Output is correct
35 Correct 76 ms 81868 KB Output is correct
36 Correct 52 ms 77884 KB Output is correct
37 Correct 110 ms 85648 KB Output is correct
38 Correct 102 ms 86424 KB Output is correct
39 Correct 101 ms 86356 KB Output is correct
40 Correct 97 ms 86396 KB Output is correct
41 Correct 91 ms 86320 KB Output is correct
42 Correct 63 ms 84172 KB Output is correct
43 Correct 77 ms 84256 KB Output is correct
44 Correct 59 ms 84172 KB Output is correct
45 Correct 124 ms 89436 KB Output is correct
46 Correct 118 ms 89388 KB Output is correct
47 Correct 454 ms 160376 KB Output is correct
48 Correct 394 ms 226708 KB Output is correct
49 Correct 344 ms 240376 KB Output is correct
50 Correct 425 ms 256476 KB Output is correct
51 Runtime error 371 ms 262144 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -