oj.uz

Submission #709917

# Submission time Handle Problem Language Result Execution time Memory
709917 2023-03-14T19:34:26 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 44276 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 = 350;
const int MAXN = 3e4 + 5;

vector<pair<int, int> > d;

int dist[MAXN][B];
vector<short> sm[MAXN];
vector<short> bg[MAXN];

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);
            bg[d[i].first].push_back(d[i].second);
        }
        else
        {
            sm[d[i].first].push_back(d[i].second);
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < B; j++)
            dist[i][j] = INF;
    priority_queue<array<int, 3> > st;
    st.push({0, d[0].first, 0});
    dist[d[0].first][0] = 0;
    while (!st.empty())
    {
        auto [dst, pos, pw] = st.top();
        dst = -dst;
        st.pop();
        if (dst > dist[pos][pw]) continue;
        if (dst != dist[pos][pw]) continue;
        if (pw > 0)
        {
            vector<array<short, 3> > to;
            if (pos - pw >= 0)
            {
                if (dist[pos - pw][pw] > dst + 1)
                {
                    //st.erase({dist[pos - pw][pw], pos - pw, pw});
                    dist[pos - pw][pw] = dst + 1;
                    st.push({-dist[pos - pw][pw], pos - pw, pw});
                }
                if (dist[pos - pw][0] > dst + 1)
                {
                    //st.erase({dist[pos - pw][0], pos - pw, 0});
                    dist[pos - pw][0] = dst + 1;
                    st.push({-dist[pos - pw][0], pos - pw, 0});
                }
            }
            if (pos + pw < n)
            {
                if (dist[pos + pw][pw] > dst + 1)
                {
                    //st.erase({dist[pos + pw][pw], pos + pw, pw});
                    dist[pos + pw][pw] = dst + 1;
                    st.push({-dist[pos + pw][pw], pos + pw, pw});
                }
                if (dist[pos + pw][0] > dst + 1)
                {
                    //st.erase({dist[pos + pw][0], pos + pw, 0});
                    dist[pos + pw][0] = dst + 1;
                    st.push({-dist[pos + pw][0], pos + pw, 0});
                }
            }
            continue;
        }
        for (auto& mv : bg[pos])
        {
            for (int j = pos, k = 0; j < n; j += mv, k++)
            {
                if (dist[j][0] > dst + k)
                {
                    dist[j][0] = dst + k;
                    st.push({-dist[j][0], j, 0});
                }
            }
            for (int j = pos, k = 0; j >= 0; j -= mv, k++)
            {
                if (dist[j][0] > dst + k)
                {
                    dist[j][0] = dst + k;
                    st.push({-dist[j][0], j, 0});
                }
            }
        }
        for (auto& mv : sm[pos])
        {
            if (dist[pos][mv] > dst + 0)
            {
                dist[pos][mv] = dst + 0;
                st.push({-dist[pos][mv], pos, mv});
            }
        }
    }
    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 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 2 ms 1876 KB Output is correct
9 Correct 1 ms 1748 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 1748 KB Output is correct
9 Correct 2 ms 1748 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1944 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct
16 Correct 1 ms 2004 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 2 ms 4052 KB Output is correct
19 Correct 2 ms 4436 KB Output is correct
20 Correct 2 ms 4436 KB Output is correct
21 Correct 1 ms 2260 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 3 ms 3924 KB Output is correct
24 Correct 4 ms 4308 KB Output is correct
25 Correct 3 ms 4444 KB Output is correct
26 Correct 3 ms 4436 KB Output is correct
27 Correct 2 ms 4436 KB Output is correct
28 Correct 3 ms 4564 KB Output is correct
29 Correct 8 ms 4504 KB Output is correct
30 Correct 4 ms 4436 KB Output is correct
31 Correct 5 ms 4512 KB Output is correct
32 Correct 5 ms 4508 KB Output is correct
33 Correct 16 ms 4564 KB Output is correct
34 Correct 16 ms 4576 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 1748 KB Output is correct
9 Correct 1 ms 1748 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 1 ms 1876 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 3 ms 1876 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct
16 Correct 1 ms 2004 KB Output is correct
17 Correct 3 ms 2772 KB Output is correct
18 Correct 2 ms 4052 KB Output is correct
19 Correct 2 ms 4436 KB Output is correct
20 Correct 3 ms 4436 KB Output is correct
21 Correct 1 ms 2260 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct
23 Correct 3 ms 3924 KB Output is correct
24 Correct 4 ms 4308 KB Output is correct
25 Correct 3 ms 4488 KB Output is correct
26 Correct 4 ms 4436 KB Output is correct
27 Correct 3 ms 4436 KB Output is correct
28 Correct 4 ms 4564 KB Output is correct
29 Correct 9 ms 4436 KB Output is correct
30 Correct 4 ms 4436 KB Output is correct
31 Correct 6 ms 4436 KB Output is correct
32 Correct 4 ms 4436 KB Output is correct
33 Correct 15 ms 4576 KB Output is correct
34 Correct 15 ms 4564 KB Output is correct
35 Correct 17 ms 4308 KB Output is correct
36 Correct 4 ms 3380 KB Output is correct
37 Correct 25 ms 5032 KB Output is correct
38 Correct 23 ms 5204 KB Output is correct
39 Correct 23 ms 5204 KB Output is correct
40 Correct 22 ms 5304 KB Output is correct
41 Correct 23 ms 5300 KB Output is correct
42 Correct 6 ms 4728 KB Output is correct
43 Correct 6 ms 4820 KB Output is correct
44 Correct 6 ms 4836 KB Output is correct
45 Correct 79 ms 5340 KB Output is correct
46 Correct 80 ms 5272 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1752 KB Output is correct
7 Correct 1 ms 1752 KB Output is correct
8 Correct 1 ms 1748 KB Output is correct
9 Correct 1 ms 1748 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 2 ms 1876 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 3 ms 1876 KB Output is correct
15 Correct 2 ms 1876 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 3 ms 2772 KB Output is correct
18 Correct 2 ms 4052 KB Output is correct
19 Correct 2 ms 4436 KB Output is correct
20 Correct 3 ms 4436 KB Output is correct
21 Correct 1 ms 2260 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct
23 Correct 3 ms 3924 KB Output is correct
24 Correct 3 ms 4308 KB Output is correct
25 Correct 3 ms 4436 KB Output is correct
26 Correct 3 ms 4436 KB Output is correct
27 Correct 3 ms 4436 KB Output is correct
28 Correct 3 ms 4436 KB Output is correct
29 Correct 9 ms 4436 KB Output is correct
30 Correct 4 ms 4428 KB Output is correct
31 Correct 6 ms 4436 KB Output is correct
32 Correct 4 ms 4436 KB Output is correct
33 Correct 17 ms 4564 KB Output is correct
34 Correct 16 ms 4576 KB Output is correct
35 Correct 18 ms 4436 KB Output is correct
36 Correct 5 ms 3284 KB Output is correct
37 Correct 25 ms 5024 KB Output is correct
38 Correct 24 ms 5268 KB Output is correct
39 Correct 23 ms 5204 KB Output is correct
40 Correct 23 ms 5208 KB Output is correct
41 Correct 25 ms 5204 KB Output is correct
42 Correct 7 ms 4828 KB Output is correct
43 Correct 8 ms 4824 KB Output is correct
44 Correct 9 ms 4820 KB Output is correct
45 Correct 83 ms 5312 KB Output is correct
46 Correct 79 ms 5292 KB Output is correct
47 Correct 109 ms 19852 KB Output is correct
48 Correct 18 ms 34280 KB Output is correct
49 Correct 20 ms 37184 KB Output is correct
50 Correct 18 ms 40404 KB Output is correct
51 Correct 63 ms 44220 KB Output is correct
52 Correct 70 ms 44276 KB Output is correct
53 Correct 29 ms 43732 KB Output is correct
54 Correct 18 ms 42716 KB Output is correct
55 Correct 20 ms 42804 KB Output is correct
56 Correct 26 ms 43992 KB Output is correct
57 Correct 91 ms 42924 KB Output is correct
58 Correct 22 ms 43092 KB Output is correct
59 Correct 29 ms 43092 KB Output is correct
60 Correct 34 ms 43172 KB Output is correct
61 Correct 30 ms 43188 KB Output is correct
62 Correct 55 ms 44116 KB Output is correct
63 Correct 201 ms 44116 KB Output is correct
64 Correct 403 ms 44112 KB Output is correct
65 Correct 841 ms 43796 KB Output is correct
66 Execution timed out 1079 ms 43612 KB Time limit exceeded
67 Halted 0 ms 0 KB -