oj.uz

Submission #709891

# Submission time Handle Problem Language Result Execution time Memory
709891 2023-03-14T18:38:27 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 593 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 = 180;
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;
        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:51:38: warning: narrowing conversion of '(i - j)' from 'int' to 'short int' [-Wnarrowing]
   51 |                 g[i][j].push_back({i - j, 0, 1});
      |                                    ~~^~~
skyscraper.cpp:52:38: warning: narrowing conversion of '(i - j)' from 'int' to 'short int' [-Wnarrowing]
   52 |                 g[i][j].push_back({i - j, j, 1});
      |                                    ~~^~~
skyscraper.cpp:52:43: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   52 |                 g[i][j].push_back({i - j, j, 1});
      |                                           ^
skyscraper.cpp:56:38: warning: narrowing conversion of '(i + j)' from 'int' to 'short int' [-Wnarrowing]
   56 |                 g[i][j].push_back({i + j, 0, 1});
      |                                    ~~^~~
skyscraper.cpp:57:38: warning: narrowing conversion of '(i + j)' from 'int' to 'short int' [-Wnarrowing]
   57 |                 g[i][j].push_back({i + j, j, 1});
      |                                    ~~^~~
skyscraper.cpp:57:43: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   57 |                 g[i][j].push_back({i + j, j, 1});
      |                                           ^
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 63 ms 127136 KB Output is correct
2 Correct 65 ms 127100 KB Output is correct
3 Correct 67 ms 127052 KB Output is correct
4 Correct 68 ms 127032 KB Output is correct
5 Correct 70 ms 127112 KB Output is correct
6 Correct 71 ms 127124 KB Output is correct
7 Correct 71 ms 127052 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 127112 KB Output is correct
2 Correct 79 ms 127132 KB Output is correct
3 Correct 64 ms 127096 KB Output is correct
4 Correct 64 ms 127124 KB Output is correct
5 Correct 66 ms 127028 KB Output is correct
6 Correct 73 ms 127052 KB Output is correct
7 Correct 78 ms 127108 KB Output is correct
8 Correct 68 ms 127144 KB Output is correct
9 Correct 65 ms 127204 KB Output is correct
10 Correct 65 ms 127380 KB Output is correct
11 Correct 66 ms 127484 KB Output is correct
12 Correct 66 ms 127460 KB Output is correct
13 Correct 76 ms 127436 KB Output is correct
14 Correct 81 ms 127472 KB Output is correct
15 Correct 66 ms 127592 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 127140 KB Output is correct
2 Correct 63 ms 127068 KB Output is correct
3 Correct 78 ms 127080 KB Output is correct
4 Correct 72 ms 127032 KB Output is correct
5 Correct 73 ms 127148 KB Output is correct
6 Correct 61 ms 127096 KB Output is correct
7 Correct 68 ms 127040 KB Output is correct
8 Correct 72 ms 127172 KB Output is correct
9 Correct 68 ms 127208 KB Output is correct
10 Correct 65 ms 127388 KB Output is correct
11 Correct 96 ms 127436 KB Output is correct
12 Correct 91 ms 127472 KB Output is correct
13 Correct 81 ms 127436 KB Output is correct
14 Correct 100 ms 127488 KB Output is correct
15 Correct 82 ms 127528 KB Output is correct
16 Correct 83 ms 128228 KB Output is correct
17 Correct 109 ms 131844 KB Output is correct
18 Correct 119 ms 138212 KB Output is correct
19 Correct 120 ms 139692 KB Output is correct
20 Correct 104 ms 139808 KB Output is correct
21 Correct 79 ms 129556 KB Output is correct
22 Correct 103 ms 138416 KB Output is correct
23 Correct 99 ms 137288 KB Output is correct
24 Correct 100 ms 139264 KB Output is correct
25 Correct 121 ms 139744 KB Output is correct
26 Correct 99 ms 139732 KB Output is correct
27 Correct 110 ms 139912 KB Output is correct
28 Correct 108 ms 139764 KB Output is correct
29 Correct 115 ms 139816 KB Output is correct
30 Correct 107 ms 139700 KB Output is correct
31 Correct 105 ms 139728 KB Output is correct
32 Correct 106 ms 139704 KB Output is correct
33 Correct 153 ms 139928 KB Output is correct
34 Correct 134 ms 139836 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 127108 KB Output is correct
2 Correct 71 ms 127024 KB Output is correct
3 Correct 62 ms 127108 KB Output is correct
4 Correct 62 ms 127140 KB Output is correct
5 Correct 62 ms 127136 KB Output is correct
6 Correct 64 ms 127060 KB Output is correct
7 Correct 67 ms 127052 KB Output is correct
8 Correct 64 ms 127136 KB Output is correct
9 Correct 66 ms 127260 KB Output is correct
10 Correct 63 ms 127360 KB Output is correct
11 Correct 69 ms 127548 KB Output is correct
12 Correct 64 ms 127472 KB Output is correct
13 Correct 64 ms 127468 KB Output is correct
14 Correct 70 ms 127564 KB Output is correct
15 Correct 65 ms 127568 KB Output is correct
16 Correct 68 ms 128204 KB Output is correct
17 Correct 80 ms 131864 KB Output is correct
18 Correct 152 ms 138132 KB Output is correct
19 Correct 97 ms 139672 KB Output is correct
20 Correct 99 ms 139884 KB Output is correct
21 Correct 68 ms 129668 KB Output is correct
22 Correct 111 ms 138392 KB Output is correct
23 Correct 97 ms 137288 KB Output is correct
24 Correct 107 ms 139212 KB Output is correct
25 Correct 112 ms 139832 KB Output is correct
26 Correct 147 ms 139692 KB Output is correct
27 Correct 96 ms 139724 KB Output is correct
28 Correct 101 ms 139952 KB Output is correct
29 Correct 114 ms 139816 KB Output is correct
30 Correct 119 ms 139776 KB Output is correct
31 Correct 129 ms 139724 KB Output is correct
32 Correct 104 ms 139728 KB Output is correct
33 Correct 130 ms 139864 KB Output is correct
34 Correct 165 ms 139980 KB Output is correct
35 Correct 129 ms 137304 KB Output is correct
36 Correct 102 ms 134220 KB Output is correct
37 Correct 160 ms 140796 KB Output is correct
38 Correct 150 ms 141292 KB Output is correct
39 Correct 147 ms 141300 KB Output is correct
40 Correct 149 ms 141328 KB Output is correct
41 Correct 168 ms 141436 KB Output is correct
42 Correct 112 ms 140176 KB Output is correct
43 Correct 123 ms 140104 KB Output is correct
44 Correct 106 ms 140156 KB Output is correct
45 Correct 224 ms 142376 KB Output is correct
46 Correct 215 ms 142528 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 127052 KB Output is correct
2 Correct 68 ms 127124 KB Output is correct
3 Correct 72 ms 127076 KB Output is correct
4 Correct 69 ms 127064 KB Output is correct
5 Correct 70 ms 127072 KB Output is correct
6 Correct 70 ms 127144 KB Output is correct
7 Correct 64 ms 127148 KB Output is correct
8 Correct 76 ms 127144 KB Output is correct
9 Correct 70 ms 127228 KB Output is correct
10 Correct 69 ms 127464 KB Output is correct
11 Correct 73 ms 127484 KB Output is correct
12 Correct 69 ms 127388 KB Output is correct
13 Correct 74 ms 127424 KB Output is correct
14 Correct 83 ms 127584 KB Output is correct
15 Correct 71 ms 127496 KB Output is correct
16 Correct 72 ms 128140 KB Output is correct
17 Correct 85 ms 131964 KB Output is correct
18 Correct 103 ms 138156 KB Output is correct
19 Correct 119 ms 139784 KB Output is correct
20 Correct 104 ms 139840 KB Output is correct
21 Correct 74 ms 129588 KB Output is correct
22 Correct 95 ms 138416 KB Output is correct
23 Correct 109 ms 137264 KB Output is correct
24 Correct 120 ms 139156 KB Output is correct
25 Correct 110 ms 139768 KB Output is correct
26 Correct 103 ms 139768 KB Output is correct
27 Correct 102 ms 139764 KB Output is correct
28 Correct 120 ms 139792 KB Output is correct
29 Correct 126 ms 139820 KB Output is correct
30 Correct 125 ms 139748 KB Output is correct
31 Correct 122 ms 139772 KB Output is correct
32 Correct 113 ms 139692 KB Output is correct
33 Correct 132 ms 139868 KB Output is correct
34 Correct 140 ms 139916 KB Output is correct
35 Correct 131 ms 137372 KB Output is correct
36 Correct 110 ms 134124 KB Output is correct
37 Correct 183 ms 140752 KB Output is correct
38 Correct 169 ms 141476 KB Output is correct
39 Correct 157 ms 141472 KB Output is correct
40 Correct 149 ms 141476 KB Output is correct
41 Correct 152 ms 141484 KB Output is correct
42 Correct 121 ms 140172 KB Output is correct
43 Correct 114 ms 140284 KB Output is correct
44 Correct 108 ms 140236 KB Output is correct
45 Correct 234 ms 142636 KB Output is correct
46 Correct 226 ms 142512 KB Output is correct
47 Correct 593 ms 209116 KB Output is correct
48 Runtime error 488 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -