oj.uz

Submission #709868

# Submission time Handle Problem Language Result Execution time Memory
709868 2023-03-14T18:08:57 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 314 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 = 173;
const int MAXN = 3e4;

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 = 0; 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());
        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 57 ms 122180 KB Output is correct
2 Correct 56 ms 122160 KB Output is correct
3 Correct 55 ms 122200 KB Output is correct
4 Correct 56 ms 122188 KB Output is correct
5 Correct 57 ms 122080 KB Output is correct
6 Correct 58 ms 122124 KB Output is correct
7 Correct 63 ms 122260 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 122196 KB Output is correct
2 Correct 60 ms 122188 KB Output is correct
3 Correct 56 ms 122120 KB Output is correct
4 Correct 64 ms 122200 KB Output is correct
5 Correct 57 ms 122164 KB Output is correct
6 Correct 74 ms 122152 KB Output is correct
7 Correct 59 ms 122120 KB Output is correct
8 Correct 59 ms 122216 KB Output is correct
9 Correct 59 ms 122232 KB Output is correct
10 Correct 58 ms 122588 KB Output is correct
11 Correct 59 ms 122712 KB Output is correct
12 Correct 59 ms 122584 KB Output is correct
13 Correct 64 ms 122540 KB Output is correct
14 Correct 59 ms 122628 KB Output is correct
15 Correct 67 ms 122700 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 122080 KB Output is correct
2 Correct 61 ms 122204 KB Output is correct
3 Correct 68 ms 122068 KB Output is correct
4 Correct 73 ms 122160 KB Output is correct
5 Correct 64 ms 122188 KB Output is correct
6 Correct 59 ms 122180 KB Output is correct
7 Correct 60 ms 122200 KB Output is correct
8 Correct 65 ms 122220 KB Output is correct
9 Correct 71 ms 122284 KB Output is correct
10 Correct 67 ms 122596 KB Output is correct
11 Correct 68 ms 122700 KB Output is correct
12 Correct 58 ms 122612 KB Output is correct
13 Correct 58 ms 122584 KB Output is correct
14 Correct 62 ms 122636 KB Output is correct
15 Correct 66 ms 122740 KB Output is correct
16 Correct 70 ms 123520 KB Output is correct
17 Correct 84 ms 129988 KB Output is correct
18 Correct 95 ms 141444 KB Output is correct
19 Correct 115 ms 144348 KB Output is correct
20 Correct 111 ms 144400 KB Output is correct
21 Correct 69 ms 125864 KB Output is correct
22 Correct 96 ms 141912 KB Output is correct
23 Correct 92 ms 139772 KB Output is correct
24 Correct 112 ms 143260 KB Output is correct
25 Correct 105 ms 144512 KB Output is correct
26 Correct 103 ms 144260 KB Output is correct
27 Correct 109 ms 144332 KB Output is correct
28 Correct 126 ms 144568 KB Output is correct
29 Correct 123 ms 144340 KB Output is correct
30 Correct 101 ms 144208 KB Output is correct
31 Correct 112 ms 144328 KB Output is correct
32 Correct 105 ms 144300 KB Output is correct
33 Correct 146 ms 144456 KB Output is correct
34 Correct 129 ms 144348 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 122188 KB Output is correct
2 Correct 58 ms 122304 KB Output is correct
3 Correct 61 ms 122092 KB Output is correct
4 Correct 73 ms 122124 KB Output is correct
5 Correct 61 ms 122188 KB Output is correct
6 Correct 61 ms 122136 KB Output is correct
7 Correct 57 ms 122144 KB Output is correct
8 Correct 61 ms 122152 KB Output is correct
9 Correct 59 ms 122232 KB Output is correct
10 Correct 61 ms 122544 KB Output is correct
11 Correct 63 ms 122632 KB Output is correct
12 Correct 71 ms 122596 KB Output is correct
13 Correct 60 ms 122624 KB Output is correct
14 Correct 60 ms 122660 KB Output is correct
15 Correct 62 ms 122720 KB Output is correct
16 Correct 66 ms 123596 KB Output is correct
17 Correct 78 ms 129884 KB Output is correct
18 Correct 96 ms 141376 KB Output is correct
19 Correct 105 ms 144352 KB Output is correct
20 Correct 103 ms 144276 KB Output is correct
21 Correct 78 ms 125864 KB Output is correct
22 Correct 115 ms 141772 KB Output is correct
23 Correct 93 ms 139724 KB Output is correct
24 Correct 108 ms 143308 KB Output is correct
25 Correct 102 ms 144392 KB Output is correct
26 Correct 112 ms 144332 KB Output is correct
27 Correct 132 ms 144268 KB Output is correct
28 Correct 111 ms 144528 KB Output is correct
29 Correct 119 ms 144352 KB Output is correct
30 Correct 106 ms 144296 KB Output is correct
31 Correct 113 ms 144296 KB Output is correct
32 Correct 105 ms 144432 KB Output is correct
33 Correct 137 ms 144336 KB Output is correct
34 Correct 144 ms 144368 KB Output is correct
35 Correct 126 ms 139596 KB Output is correct
36 Correct 87 ms 134076 KB Output is correct
37 Correct 167 ms 145796 KB Output is correct
38 Correct 151 ms 146932 KB Output is correct
39 Correct 155 ms 147060 KB Output is correct
40 Correct 147 ms 146912 KB Output is correct
41 Correct 142 ms 146864 KB Output is correct
42 Correct 111 ms 144900 KB Output is correct
43 Correct 109 ms 144844 KB Output is correct
44 Correct 134 ms 144876 KB Output is correct
45 Correct 219 ms 148160 KB Output is correct
46 Correct 214 ms 148144 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 122188 KB Output is correct
2 Correct 77 ms 122184 KB Output is correct
3 Correct 59 ms 122120 KB Output is correct
4 Correct 76 ms 122184 KB Output is correct
5 Correct 55 ms 122088 KB Output is correct
6 Correct 56 ms 122180 KB Output is correct
7 Correct 72 ms 122156 KB Output is correct
8 Correct 61 ms 122188 KB Output is correct
9 Correct 62 ms 122336 KB Output is correct
10 Correct 55 ms 122604 KB Output is correct
11 Correct 68 ms 122652 KB Output is correct
12 Correct 58 ms 122572 KB Output is correct
13 Correct 72 ms 122496 KB Output is correct
14 Correct 74 ms 122700 KB Output is correct
15 Correct 77 ms 122744 KB Output is correct
16 Correct 69 ms 123492 KB Output is correct
17 Correct 79 ms 129984 KB Output is correct
18 Correct 112 ms 141360 KB Output is correct
19 Correct 113 ms 144252 KB Output is correct
20 Correct 120 ms 144360 KB Output is correct
21 Correct 74 ms 125756 KB Output is correct
22 Correct 100 ms 141836 KB Output is correct
23 Correct 106 ms 139768 KB Output is correct
24 Correct 126 ms 143352 KB Output is correct
25 Correct 117 ms 144384 KB Output is correct
26 Correct 125 ms 144308 KB Output is correct
27 Correct 115 ms 144336 KB Output is correct
28 Correct 119 ms 144480 KB Output is correct
29 Correct 132 ms 144252 KB Output is correct
30 Correct 119 ms 144236 KB Output is correct
31 Correct 128 ms 144252 KB Output is correct
32 Correct 118 ms 144316 KB Output is correct
33 Correct 155 ms 144460 KB Output is correct
34 Correct 144 ms 144356 KB Output is correct
35 Correct 132 ms 139700 KB Output is correct
36 Correct 95 ms 134180 KB Output is correct
37 Correct 193 ms 145752 KB Output is correct
38 Correct 155 ms 146936 KB Output is correct
39 Correct 163 ms 146948 KB Output is correct
40 Correct 182 ms 146904 KB Output is correct
41 Correct 177 ms 146892 KB Output is correct
42 Correct 127 ms 144800 KB Output is correct
43 Correct 124 ms 144828 KB Output is correct
44 Correct 108 ms 144936 KB Output is correct
45 Correct 237 ms 148164 KB Output is correct
46 Correct 252 ms 148160 KB Output is correct
47 Runtime error 314 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -