oj.uz

Submission #709907

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

vector<pair<int, int> > d;

int dist[MAXN][B];
vector<array<short, 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;
        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.insert({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.insert({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.insert({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.insert({dist[pos + pw][0], pos + pw, 0});
                }
            }
        }
        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)
*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:43:42: warning: narrowing conversion of 'd.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)i)).std::pair<int, int>::first' from 'int' to 'short int' [-Wnarrowing]
   43 |         g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
skyscraper.cpp:43:54: warning: narrowing conversion of 'd.std::vector<std::pair<int, int> >::operator[](((std::vector<std::pair<int, int> >::size_type)i)).std::pair<int, int>::second' from 'int' to 'short int' [-Wnarrowing]
   43 |         g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
skyscraper.cpp:65:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   65 |             g[d[i].first][0].push_back({j, 0, k});
      |                                         ^
skyscraper.cpp:65:47: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
   65 |             g[d[i].first][0].push_back({j, 0, k});
      |                                               ^
skyscraper.cpp:69:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   69 |             g[d[i].first][0].push_back({j, 0, k});
      |                                         ^
skyscraper.cpp:69:47: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
   69 |             g[d[i].first][0].push_back({j, 0, k});
      |                                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 176404 KB Output is correct
2 Correct 82 ms 176352 KB Output is correct
3 Correct 81 ms 176396 KB Output is correct
4 Correct 81 ms 176376 KB Output is correct
5 Correct 81 ms 176524 KB Output is correct
6 Correct 78 ms 176440 KB Output is correct
7 Correct 88 ms 176392 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 176456 KB Output is correct
2 Correct 85 ms 176360 KB Output is correct
3 Correct 81 ms 176332 KB Output is correct
4 Correct 84 ms 176376 KB Output is correct
5 Correct 78 ms 176440 KB Output is correct
6 Correct 77 ms 176412 KB Output is correct
7 Correct 87 ms 176460 KB Output is correct
8 Correct 79 ms 176380 KB Output is correct
9 Correct 81 ms 176516 KB Output is correct
10 Correct 78 ms 176512 KB Output is correct
11 Correct 81 ms 176664 KB Output is correct
12 Correct 78 ms 176588 KB Output is correct
13 Correct 80 ms 176588 KB Output is correct
14 Correct 81 ms 176692 KB Output is correct
15 Correct 87 ms 176676 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 176420 KB Output is correct
2 Correct 87 ms 176340 KB Output is correct
3 Correct 81 ms 176432 KB Output is correct
4 Correct 80 ms 176460 KB Output is correct
5 Correct 80 ms 176404 KB Output is correct
6 Correct 81 ms 176408 KB Output is correct
7 Correct 82 ms 176476 KB Output is correct
8 Correct 82 ms 176388 KB Output is correct
9 Correct 77 ms 176492 KB Output is correct
10 Correct 80 ms 176460 KB Output is correct
11 Correct 78 ms 176580 KB Output is correct
12 Correct 79 ms 176572 KB Output is correct
13 Correct 88 ms 176532 KB Output is correct
14 Correct 80 ms 176660 KB Output is correct
15 Correct 80 ms 176644 KB Output is correct
16 Correct 79 ms 176660 KB Output is correct
17 Correct 89 ms 177224 KB Output is correct
18 Correct 81 ms 178316 KB Output is correct
19 Correct 85 ms 178424 KB Output is correct
20 Correct 84 ms 178444 KB Output is correct
21 Correct 83 ms 176808 KB Output is correct
22 Correct 80 ms 178180 KB Output is correct
23 Correct 81 ms 178080 KB Output is correct
24 Correct 87 ms 178492 KB Output is correct
25 Correct 87 ms 178468 KB Output is correct
26 Correct 80 ms 178520 KB Output is correct
27 Correct 79 ms 178380 KB Output is correct
28 Correct 82 ms 178536 KB Output is correct
29 Correct 95 ms 178388 KB Output is correct
30 Correct 87 ms 178416 KB Output is correct
31 Correct 92 ms 178388 KB Output is correct
32 Correct 90 ms 178416 KB Output is correct
33 Correct 119 ms 178496 KB Output is correct
34 Correct 105 ms 178508 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 176364 KB Output is correct
2 Correct 84 ms 176456 KB Output is correct
3 Correct 84 ms 176352 KB Output is correct
4 Correct 80 ms 176416 KB Output is correct
5 Correct 80 ms 176396 KB Output is correct
6 Correct 84 ms 176420 KB Output is correct
7 Correct 82 ms 176440 KB Output is correct
8 Correct 79 ms 176472 KB Output is correct
9 Correct 79 ms 176404 KB Output is correct
10 Correct 85 ms 176572 KB Output is correct
11 Correct 80 ms 176672 KB Output is correct
12 Correct 90 ms 176492 KB Output is correct
13 Correct 80 ms 176580 KB Output is correct
14 Correct 82 ms 176704 KB Output is correct
15 Correct 83 ms 176612 KB Output is correct
16 Correct 82 ms 176568 KB Output is correct
17 Correct 95 ms 177336 KB Output is correct
18 Correct 82 ms 178188 KB Output is correct
19 Correct 83 ms 178448 KB Output is correct
20 Correct 83 ms 178500 KB Output is correct
21 Correct 81 ms 176844 KB Output is correct
22 Correct 85 ms 178204 KB Output is correct
23 Correct 88 ms 178192 KB Output is correct
24 Correct 93 ms 178328 KB Output is correct
25 Correct 87 ms 178392 KB Output is correct
26 Correct 81 ms 178384 KB Output is correct
27 Correct 82 ms 178468 KB Output is correct
28 Correct 85 ms 178444 KB Output is correct
29 Correct 90 ms 178408 KB Output is correct
30 Correct 83 ms 178368 KB Output is correct
31 Correct 85 ms 178444 KB Output is correct
32 Correct 87 ms 178380 KB Output is correct
33 Correct 111 ms 178508 KB Output is correct
34 Correct 108 ms 178508 KB Output is correct
35 Correct 103 ms 179012 KB Output is correct
36 Correct 85 ms 177756 KB Output is correct
37 Correct 120 ms 179844 KB Output is correct
38 Correct 114 ms 179952 KB Output is correct
39 Correct 114 ms 179932 KB Output is correct
40 Correct 115 ms 180044 KB Output is correct
41 Correct 110 ms 179916 KB Output is correct
42 Correct 84 ms 179040 KB Output is correct
43 Correct 98 ms 178948 KB Output is correct
44 Correct 88 ms 178956 KB Output is correct
45 Correct 209 ms 180788 KB Output is correct
46 Correct 199 ms 180864 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 176528 KB Output is correct
2 Correct 82 ms 176380 KB Output is correct
3 Correct 79 ms 176460 KB Output is correct
4 Correct 81 ms 176464 KB Output is correct
5 Correct 80 ms 176368 KB Output is correct
6 Correct 81 ms 176352 KB Output is correct
7 Correct 79 ms 176468 KB Output is correct
8 Correct 79 ms 176536 KB Output is correct
9 Correct 86 ms 176416 KB Output is correct
10 Correct 84 ms 176520 KB Output is correct
11 Correct 81 ms 176620 KB Output is correct
12 Correct 80 ms 176588 KB Output is correct
13 Correct 81 ms 176588 KB Output is correct
14 Correct 81 ms 176796 KB Output is correct
15 Correct 81 ms 176616 KB Output is correct
16 Correct 82 ms 176648 KB Output is correct
17 Correct 90 ms 177356 KB Output is correct
18 Correct 81 ms 178316 KB Output is correct
19 Correct 84 ms 178552 KB Output is correct
20 Correct 82 ms 178460 KB Output is correct
21 Correct 95 ms 176840 KB Output is correct
22 Correct 85 ms 178120 KB Output is correct
23 Correct 85 ms 178000 KB Output is correct
24 Correct 89 ms 178440 KB Output is correct
25 Correct 81 ms 178440 KB Output is correct
26 Correct 84 ms 178416 KB Output is correct
27 Correct 83 ms 178380 KB Output is correct
28 Correct 84 ms 178480 KB Output is correct
29 Correct 94 ms 178564 KB Output is correct
30 Correct 84 ms 178400 KB Output is correct
31 Correct 90 ms 178464 KB Output is correct
32 Correct 85 ms 178576 KB Output is correct
33 Correct 101 ms 178584 KB Output is correct
34 Correct 110 ms 178508 KB Output is correct
35 Correct 101 ms 178976 KB Output is correct
36 Correct 96 ms 177752 KB Output is correct
37 Correct 117 ms 179788 KB Output is correct
38 Correct 115 ms 179892 KB Output is correct
39 Correct 118 ms 179980 KB Output is correct
40 Correct 118 ms 179992 KB Output is correct
41 Correct 113 ms 180044 KB Output is correct
42 Correct 86 ms 178968 KB Output is correct
43 Correct 94 ms 179036 KB Output is correct
44 Correct 85 ms 179008 KB Output is correct
45 Correct 200 ms 180704 KB Output is correct
46 Correct 205 ms 180828 KB Output is correct
47 Correct 239 ms 192280 KB Output is correct
48 Correct 97 ms 200632 KB Output is correct
49 Correct 102 ms 202536 KB Output is correct
50 Correct 110 ms 204752 KB Output is correct
51 Correct 167 ms 208524 KB Output is correct
52 Correct 174 ms 208532 KB Output is correct
53 Correct 115 ms 206880 KB Output is correct
54 Correct 103 ms 205688 KB Output is correct
55 Correct 97 ms 205704 KB Output is correct
56 Correct 106 ms 206984 KB Output is correct
57 Correct 218 ms 205880 KB Output is correct
58 Correct 107 ms 206348 KB Output is correct
59 Correct 112 ms 206320 KB Output is correct
60 Correct 121 ms 206464 KB Output is correct
61 Correct 112 ms 206360 KB Output is correct
62 Correct 160 ms 208468 KB Output is correct
63 Correct 285 ms 223652 KB Output is correct
64 Correct 363 ms 223820 KB Output is correct
65 Correct 931 ms 220552 KB Output is correct
66 Execution timed out 1091 ms 208192 KB Time limit exceeded
67 Halted 0 ms 0 KB -