oj.uz

Submission #709872

# Submission time Handle Problem Language Result Execution time Memory
709872 2023-03-14T18:27:14 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 269 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 + 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 55 ms 122160 KB Output is correct
2 Correct 56 ms 122188 KB Output is correct
3 Correct 62 ms 122168 KB Output is correct
4 Correct 58 ms 122196 KB Output is correct
5 Correct 65 ms 122220 KB Output is correct
6 Correct 61 ms 122188 KB Output is correct
7 Correct 56 ms 122096 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 122184 KB Output is correct
2 Correct 67 ms 122212 KB Output is correct
3 Correct 59 ms 122100 KB Output is correct
4 Correct 58 ms 122140 KB Output is correct
5 Correct 58 ms 122220 KB Output is correct
6 Correct 57 ms 122144 KB Output is correct
7 Correct 56 ms 122220 KB Output is correct
8 Correct 59 ms 122388 KB Output is correct
9 Correct 58 ms 122316 KB Output is correct
10 Correct 64 ms 122572 KB Output is correct
11 Correct 64 ms 122644 KB Output is correct
12 Correct 66 ms 122568 KB Output is correct
13 Correct 56 ms 122528 KB Output is correct
14 Correct 58 ms 122724 KB Output is correct
15 Correct 61 ms 122700 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 122212 KB Output is correct
2 Correct 59 ms 122200 KB Output is correct
3 Correct 57 ms 122100 KB Output is correct
4 Correct 65 ms 122204 KB Output is correct
5 Correct 59 ms 122148 KB Output is correct
6 Correct 61 ms 122180 KB Output is correct
7 Correct 56 ms 122188 KB Output is correct
8 Correct 59 ms 122152 KB Output is correct
9 Correct 59 ms 122228 KB Output is correct
10 Correct 63 ms 122544 KB Output is correct
11 Correct 63 ms 122708 KB Output is correct
12 Correct 57 ms 122632 KB Output is correct
13 Correct 58 ms 122536 KB Output is correct
14 Correct 58 ms 122760 KB Output is correct
15 Correct 64 ms 122748 KB Output is correct
16 Correct 60 ms 123528 KB Output is correct
17 Correct 82 ms 129952 KB Output is correct
18 Correct 95 ms 141356 KB Output is correct
19 Correct 98 ms 144160 KB Output is correct
20 Correct 97 ms 144224 KB Output is correct
21 Correct 70 ms 125736 KB Output is correct
22 Correct 98 ms 141644 KB Output is correct
23 Correct 93 ms 139576 KB Output is correct
24 Correct 102 ms 143212 KB Output is correct
25 Correct 97 ms 144220 KB Output is correct
26 Correct 123 ms 144148 KB Output is correct
27 Correct 106 ms 144264 KB Output is correct
28 Correct 103 ms 144312 KB Output is correct
29 Correct 115 ms 144240 KB Output is correct
30 Correct 108 ms 144172 KB Output is correct
31 Correct 111 ms 144232 KB Output is correct
32 Correct 100 ms 144336 KB Output is correct
33 Correct 136 ms 144256 KB Output is correct
34 Correct 137 ms 144276 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 122156 KB Output is correct
2 Correct 57 ms 122192 KB Output is correct
3 Correct 59 ms 122132 KB Output is correct
4 Correct 60 ms 122208 KB Output is correct
5 Correct 60 ms 122172 KB Output is correct
6 Correct 68 ms 122112 KB Output is correct
7 Correct 72 ms 122140 KB Output is correct
8 Correct 57 ms 122212 KB Output is correct
9 Correct 58 ms 122256 KB Output is correct
10 Correct 61 ms 122696 KB Output is correct
11 Correct 60 ms 122672 KB Output is correct
12 Correct 64 ms 122552 KB Output is correct
13 Correct 63 ms 122716 KB Output is correct
14 Correct 60 ms 122700 KB Output is correct
15 Correct 59 ms 122672 KB Output is correct
16 Correct 59 ms 123596 KB Output is correct
17 Correct 75 ms 129868 KB Output is correct
18 Correct 89 ms 141224 KB Output is correct
19 Correct 106 ms 144184 KB Output is correct
20 Correct 110 ms 144204 KB Output is correct
21 Correct 64 ms 125840 KB Output is correct
22 Correct 91 ms 141704 KB Output is correct
23 Correct 87 ms 139584 KB Output is correct
24 Correct 119 ms 143136 KB Output is correct
25 Correct 110 ms 144324 KB Output is correct
26 Correct 96 ms 144228 KB Output is correct
27 Correct 99 ms 144136 KB Output is correct
28 Correct 128 ms 144212 KB Output is correct
29 Correct 115 ms 144248 KB Output is correct
30 Correct 101 ms 144064 KB Output is correct
31 Correct 108 ms 144168 KB Output is correct
32 Correct 104 ms 144216 KB Output is correct
33 Correct 134 ms 144324 KB Output is correct
34 Correct 127 ms 144364 KB Output is correct
35 Correct 114 ms 139480 KB Output is correct
36 Correct 85 ms 133996 KB Output is correct
37 Correct 155 ms 145616 KB Output is correct
38 Correct 142 ms 146636 KB Output is correct
39 Correct 142 ms 146612 KB Output is correct
40 Correct 147 ms 146600 KB Output is correct
41 Correct 178 ms 146672 KB Output is correct
42 Correct 99 ms 144656 KB Output is correct
43 Correct 105 ms 144716 KB Output is correct
44 Correct 102 ms 144800 KB Output is correct
45 Correct 206 ms 148052 KB Output is correct
46 Correct 192 ms 148068 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 122140 KB Output is correct
2 Correct 60 ms 122260 KB Output is correct
3 Correct 65 ms 122208 KB Output is correct
4 Correct 64 ms 122172 KB Output is correct
5 Correct 55 ms 122188 KB Output is correct
6 Correct 57 ms 122212 KB Output is correct
7 Correct 59 ms 122216 KB Output is correct
8 Correct 58 ms 122204 KB Output is correct
9 Correct 75 ms 122264 KB Output is correct
10 Correct 58 ms 122560 KB Output is correct
11 Correct 60 ms 122588 KB Output is correct
12 Correct 58 ms 122632 KB Output is correct
13 Correct 59 ms 122592 KB Output is correct
14 Correct 62 ms 122764 KB Output is correct
15 Correct 68 ms 122780 KB Output is correct
16 Correct 62 ms 123556 KB Output is correct
17 Correct 74 ms 129952 KB Output is correct
18 Correct 93 ms 141344 KB Output is correct
19 Correct 105 ms 144172 KB Output is correct
20 Correct 106 ms 144204 KB Output is correct
21 Correct 73 ms 125828 KB Output is correct
22 Correct 91 ms 141648 KB Output is correct
23 Correct 91 ms 139720 KB Output is correct
24 Correct 104 ms 143212 KB Output is correct
25 Correct 97 ms 144216 KB Output is correct
26 Correct 97 ms 144144 KB Output is correct
27 Correct 128 ms 144164 KB Output is correct
28 Correct 114 ms 144324 KB Output is correct
29 Correct 124 ms 144204 KB Output is correct
30 Correct 110 ms 144184 KB Output is correct
31 Correct 108 ms 144204 KB Output is correct
32 Correct 110 ms 144344 KB Output is correct
33 Correct 126 ms 144332 KB Output is correct
34 Correct 139 ms 144444 KB Output is correct
35 Correct 137 ms 139468 KB Output is correct
36 Correct 85 ms 134028 KB Output is correct
37 Correct 156 ms 145700 KB Output is correct
38 Correct 145 ms 146624 KB Output is correct
39 Correct 148 ms 146540 KB Output is correct
40 Correct 140 ms 146580 KB Output is correct
41 Correct 173 ms 146776 KB Output is correct
42 Correct 113 ms 144748 KB Output is correct
43 Correct 100 ms 144712 KB Output is correct
44 Correct 97 ms 144704 KB Output is correct
45 Correct 208 ms 148048 KB Output is correct
46 Correct 206 ms 148160 KB Output is correct
47 Runtime error 269 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -