oj.uz

Submission #709892

# Submission time Handle Problem Language Result Execution time Memory
709892 2023-03-14T18:38:45 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 530 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 = 160;
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 56 ms 112968 KB Output is correct
2 Correct 64 ms 113000 KB Output is correct
3 Correct 62 ms 113120 KB Output is correct
4 Correct 53 ms 112968 KB Output is correct
5 Correct 57 ms 112992 KB Output is correct
6 Correct 61 ms 112984 KB Output is correct
7 Correct 56 ms 113048 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 112980 KB Output is correct
2 Correct 64 ms 113044 KB Output is correct
3 Correct 58 ms 113012 KB Output is correct
4 Correct 62 ms 113148 KB Output is correct
5 Correct 65 ms 113000 KB Output is correct
6 Correct 64 ms 112960 KB Output is correct
7 Correct 65 ms 112936 KB Output is correct
8 Correct 59 ms 113032 KB Output is correct
9 Correct 58 ms 113056 KB Output is correct
10 Correct 53 ms 113356 KB Output is correct
11 Correct 78 ms 113424 KB Output is correct
12 Correct 62 ms 113308 KB Output is correct
13 Correct 64 ms 113328 KB Output is correct
14 Correct 60 ms 113408 KB Output is correct
15 Correct 67 ms 113492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 113044 KB Output is correct
2 Correct 61 ms 113100 KB Output is correct
3 Correct 61 ms 112924 KB Output is correct
4 Correct 62 ms 112968 KB Output is correct
5 Correct 60 ms 113032 KB Output is correct
6 Correct 55 ms 112972 KB Output is correct
7 Correct 60 ms 112960 KB Output is correct
8 Correct 57 ms 113040 KB Output is correct
9 Correct 57 ms 113092 KB Output is correct
10 Correct 58 ms 113268 KB Output is correct
11 Correct 68 ms 113368 KB Output is correct
12 Correct 65 ms 113376 KB Output is correct
13 Correct 56 ms 113288 KB Output is correct
14 Correct 71 ms 113400 KB Output is correct
15 Correct 67 ms 113404 KB Output is correct
16 Correct 61 ms 114056 KB Output is correct
17 Correct 81 ms 117324 KB Output is correct
18 Correct 93 ms 122852 KB Output is correct
19 Correct 96 ms 124208 KB Output is correct
20 Correct 99 ms 124240 KB Output is correct
21 Correct 74 ms 115276 KB Output is correct
22 Correct 91 ms 123040 KB Output is correct
23 Correct 100 ms 121936 KB Output is correct
24 Correct 110 ms 123736 KB Output is correct
25 Correct 108 ms 124248 KB Output is correct
26 Correct 121 ms 124292 KB Output is correct
27 Correct 105 ms 124304 KB Output is correct
28 Correct 115 ms 124308 KB Output is correct
29 Correct 114 ms 124216 KB Output is correct
30 Correct 109 ms 124236 KB Output is correct
31 Correct 104 ms 124260 KB Output is correct
32 Correct 119 ms 124300 KB Output is correct
33 Correct 126 ms 124412 KB Output is correct
34 Correct 147 ms 124328 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 112976 KB Output is correct
2 Correct 55 ms 113008 KB Output is correct
3 Correct 60 ms 112988 KB Output is correct
4 Correct 55 ms 112940 KB Output is correct
5 Correct 51 ms 112992 KB Output is correct
6 Correct 53 ms 112964 KB Output is correct
7 Correct 59 ms 113004 KB Output is correct
8 Correct 63 ms 113040 KB Output is correct
9 Correct 56 ms 113164 KB Output is correct
10 Correct 57 ms 113368 KB Output is correct
11 Correct 62 ms 113328 KB Output is correct
12 Correct 59 ms 113316 KB Output is correct
13 Correct 60 ms 113292 KB Output is correct
14 Correct 63 ms 113432 KB Output is correct
15 Correct 68 ms 113496 KB Output is correct
16 Correct 60 ms 114032 KB Output is correct
17 Correct 83 ms 117240 KB Output is correct
18 Correct 93 ms 122896 KB Output is correct
19 Correct 90 ms 124288 KB Output is correct
20 Correct 95 ms 124296 KB Output is correct
21 Correct 61 ms 115292 KB Output is correct
22 Correct 85 ms 123072 KB Output is correct
23 Correct 83 ms 122004 KB Output is correct
24 Correct 92 ms 123852 KB Output is correct
25 Correct 105 ms 124404 KB Output is correct
26 Correct 90 ms 124236 KB Output is correct
27 Correct 90 ms 124240 KB Output is correct
28 Correct 94 ms 124368 KB Output is correct
29 Correct 110 ms 124288 KB Output is correct
30 Correct 101 ms 124180 KB Output is correct
31 Correct 96 ms 124312 KB Output is correct
32 Correct 100 ms 124284 KB Output is correct
33 Correct 119 ms 124544 KB Output is correct
34 Correct 121 ms 124376 KB Output is correct
35 Correct 107 ms 122340 KB Output is correct
36 Correct 77 ms 119380 KB Output is correct
37 Correct 156 ms 125332 KB Output is correct
38 Correct 143 ms 125912 KB Output is correct
39 Correct 138 ms 125900 KB Output is correct
40 Correct 137 ms 126048 KB Output is correct
41 Correct 133 ms 126120 KB Output is correct
42 Correct 103 ms 124856 KB Output is correct
43 Correct 104 ms 124896 KB Output is correct
44 Correct 94 ms 124836 KB Output is correct
45 Correct 183 ms 127144 KB Output is correct
46 Correct 183 ms 127512 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 112984 KB Output is correct
2 Correct 54 ms 113048 KB Output is correct
3 Correct 57 ms 113044 KB Output is correct
4 Correct 54 ms 112972 KB Output is correct
5 Correct 55 ms 113044 KB Output is correct
6 Correct 54 ms 113056 KB Output is correct
7 Correct 57 ms 113052 KB Output is correct
8 Correct 55 ms 113100 KB Output is correct
9 Correct 56 ms 113124 KB Output is correct
10 Correct 62 ms 113352 KB Output is correct
11 Correct 59 ms 113448 KB Output is correct
12 Correct 56 ms 113384 KB Output is correct
13 Correct 66 ms 113412 KB Output is correct
14 Correct 58 ms 113504 KB Output is correct
15 Correct 56 ms 113492 KB Output is correct
16 Correct 58 ms 114076 KB Output is correct
17 Correct 72 ms 117360 KB Output is correct
18 Correct 84 ms 122808 KB Output is correct
19 Correct 91 ms 124404 KB Output is correct
20 Correct 93 ms 124352 KB Output is correct
21 Correct 69 ms 115304 KB Output is correct
22 Correct 86 ms 123008 KB Output is correct
23 Correct 91 ms 122036 KB Output is correct
24 Correct 91 ms 123800 KB Output is correct
25 Correct 98 ms 124264 KB Output is correct
26 Correct 105 ms 124196 KB Output is correct
27 Correct 93 ms 124252 KB Output is correct
28 Correct 95 ms 124340 KB Output is correct
29 Correct 116 ms 124232 KB Output is correct
30 Correct 96 ms 124192 KB Output is correct
31 Correct 101 ms 124276 KB Output is correct
32 Correct 99 ms 124252 KB Output is correct
33 Correct 128 ms 124552 KB Output is correct
34 Correct 118 ms 124428 KB Output is correct
35 Correct 109 ms 122432 KB Output is correct
36 Correct 79 ms 119320 KB Output is correct
37 Correct 175 ms 125404 KB Output is correct
38 Correct 135 ms 125996 KB Output is correct
39 Correct 136 ms 126124 KB Output is correct
40 Correct 136 ms 126112 KB Output is correct
41 Correct 136 ms 126076 KB Output is correct
42 Correct 102 ms 124940 KB Output is correct
43 Correct 102 ms 124816 KB Output is correct
44 Correct 101 ms 124856 KB Output is correct
45 Correct 179 ms 127268 KB Output is correct
46 Correct 211 ms 127436 KB Output is correct
47 Correct 519 ms 186688 KB Output is correct
48 Correct 530 ms 244940 KB Output is correct
49 Correct 512 ms 256828 KB Output is correct
50 Runtime error 487 ms 262144 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -