oj.uz

Submission #709900

# Submission time Handle Problem Language Result Execution time Memory
709900 2023-03-14T19:01:21 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 145280 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 = 140;
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)
            {
                short pos1 = pos - pw;
                to.push_back({pos1, pw, 1});
                to.push_back({pos1, 0, 1});
            }
            if (pos + pw < n)
            {
                short pos1 = pos + pw;
                to.push_back({pos1, pw, 1});
                to.push_back({pos1, 0, 1});
            }
            for (auto& [psu, pwu, w] : to)
            {
                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});
                }
            }
        }
        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});
      |                                               ^
skyscraper.cpp:86:37: warning: narrowing conversion of 'pw' from 'std::tuple_element<2, std::array<int, 3> >::type' {aka 'int'} to 'short int' [-Wnarrowing]
   86 |                 to.push_back({pos1, pw, 1});
      |                                     ^~
skyscraper.cpp:92:37: warning: narrowing conversion of 'pw' from 'std::tuple_element<2, std::array<int, 3> >::type' {aka 'int'} to 'short int' [-Wnarrowing]
   92 |                 to.push_back({pos1, pw, 1});
      |                                     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98908 KB Output is correct
2 Correct 44 ms 98944 KB Output is correct
3 Correct 44 ms 98948 KB Output is correct
4 Correct 45 ms 98876 KB Output is correct
5 Correct 45 ms 98876 KB Output is correct
6 Correct 47 ms 98920 KB Output is correct
7 Correct 48 ms 98920 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98880 KB Output is correct
2 Correct 46 ms 98848 KB Output is correct
3 Correct 47 ms 98896 KB Output is correct
4 Correct 49 ms 98952 KB Output is correct
5 Correct 50 ms 98964 KB Output is correct
6 Correct 50 ms 98956 KB Output is correct
7 Correct 47 ms 98900 KB Output is correct
8 Correct 48 ms 98968 KB Output is correct
9 Correct 47 ms 98996 KB Output is correct
10 Correct 47 ms 99028 KB Output is correct
11 Correct 56 ms 99108 KB Output is correct
12 Correct 49 ms 98992 KB Output is correct
13 Correct 51 ms 99020 KB Output is correct
14 Correct 48 ms 99148 KB Output is correct
15 Correct 47 ms 99164 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98892 KB Output is correct
2 Correct 46 ms 98896 KB Output is correct
3 Correct 45 ms 98880 KB Output is correct
4 Correct 48 ms 98852 KB Output is correct
5 Correct 46 ms 98900 KB Output is correct
6 Correct 45 ms 98988 KB Output is correct
7 Correct 52 ms 98860 KB Output is correct
8 Correct 46 ms 98888 KB Output is correct
9 Correct 47 ms 98904 KB Output is correct
10 Correct 52 ms 98924 KB Output is correct
11 Correct 46 ms 99020 KB Output is correct
12 Correct 47 ms 98956 KB Output is correct
13 Correct 50 ms 99000 KB Output is correct
14 Correct 55 ms 99096 KB Output is correct
15 Correct 48 ms 99148 KB Output is correct
16 Correct 48 ms 99080 KB Output is correct
17 Correct 60 ms 99404 KB Output is correct
18 Correct 47 ms 99932 KB Output is correct
19 Correct 50 ms 100044 KB Output is correct
20 Correct 53 ms 100076 KB Output is correct
21 Correct 53 ms 99172 KB Output is correct
22 Correct 48 ms 100080 KB Output is correct
23 Correct 49 ms 99844 KB Output is correct
24 Correct 49 ms 100048 KB Output is correct
25 Correct 48 ms 100064 KB Output is correct
26 Correct 49 ms 100104 KB Output is correct
27 Correct 50 ms 99988 KB Output is correct
28 Correct 55 ms 100108 KB Output is correct
29 Correct 64 ms 100112 KB Output is correct
30 Correct 52 ms 99968 KB Output is correct
31 Correct 56 ms 100040 KB Output is correct
32 Correct 53 ms 100104 KB Output is correct
33 Correct 80 ms 100212 KB Output is correct
34 Correct 87 ms 100324 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 98924 KB Output is correct
2 Correct 47 ms 98888 KB Output is correct
3 Correct 47 ms 98900 KB Output is correct
4 Correct 46 ms 98952 KB Output is correct
5 Correct 51 ms 98952 KB Output is correct
6 Correct 46 ms 98900 KB Output is correct
7 Correct 47 ms 98840 KB Output is correct
8 Correct 48 ms 98880 KB Output is correct
9 Correct 50 ms 98892 KB Output is correct
10 Correct 46 ms 98992 KB Output is correct
11 Correct 49 ms 99036 KB Output is correct
12 Correct 46 ms 98944 KB Output is correct
13 Correct 47 ms 99020 KB Output is correct
14 Correct 48 ms 99164 KB Output is correct
15 Correct 50 ms 99156 KB Output is correct
16 Correct 53 ms 98992 KB Output is correct
17 Correct 56 ms 99464 KB Output is correct
18 Correct 49 ms 99904 KB Output is correct
19 Correct 48 ms 100008 KB Output is correct
20 Correct 48 ms 100124 KB Output is correct
21 Correct 56 ms 99216 KB Output is correct
22 Correct 48 ms 99904 KB Output is correct
23 Correct 52 ms 99792 KB Output is correct
24 Correct 55 ms 100048 KB Output is correct
25 Correct 49 ms 100024 KB Output is correct
26 Correct 51 ms 100044 KB Output is correct
27 Correct 49 ms 100012 KB Output is correct
28 Correct 53 ms 100088 KB Output is correct
29 Correct 72 ms 100028 KB Output is correct
30 Correct 59 ms 100044 KB Output is correct
31 Correct 58 ms 100024 KB Output is correct
32 Correct 55 ms 100096 KB Output is correct
33 Correct 81 ms 100164 KB Output is correct
34 Correct 89 ms 100108 KB Output is correct
35 Correct 72 ms 100940 KB Output is correct
36 Correct 56 ms 99676 KB Output is correct
37 Correct 93 ms 101440 KB Output is correct
38 Correct 83 ms 101660 KB Output is correct
39 Correct 85 ms 101588 KB Output is correct
40 Correct 81 ms 101576 KB Output is correct
41 Correct 96 ms 101636 KB Output is correct
42 Correct 56 ms 100532 KB Output is correct
43 Correct 52 ms 100612 KB Output is correct
44 Correct 52 ms 100584 KB Output is correct
45 Correct 137 ms 103208 KB Output is correct
46 Correct 158 ms 103296 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98928 KB Output is correct
2 Correct 47 ms 98884 KB Output is correct
3 Correct 52 ms 98872 KB Output is correct
4 Correct 46 ms 98900 KB Output is correct
5 Correct 46 ms 98960 KB Output is correct
6 Correct 48 ms 98848 KB Output is correct
7 Correct 47 ms 98916 KB Output is correct
8 Correct 57 ms 98904 KB Output is correct
9 Correct 46 ms 98892 KB Output is correct
10 Correct 49 ms 99036 KB Output is correct
11 Correct 49 ms 99080 KB Output is correct
12 Correct 47 ms 99028 KB Output is correct
13 Correct 54 ms 99020 KB Output is correct
14 Correct 48 ms 99060 KB Output is correct
15 Correct 50 ms 99080 KB Output is correct
16 Correct 47 ms 99000 KB Output is correct
17 Correct 51 ms 99444 KB Output is correct
18 Correct 46 ms 99896 KB Output is correct
19 Correct 48 ms 99976 KB Output is correct
20 Correct 58 ms 100068 KB Output is correct
21 Correct 51 ms 99184 KB Output is correct
22 Correct 48 ms 99948 KB Output is correct
23 Correct 51 ms 99848 KB Output is correct
24 Correct 51 ms 100060 KB Output is correct
25 Correct 50 ms 100148 KB Output is correct
26 Correct 50 ms 100000 KB Output is correct
27 Correct 49 ms 100044 KB Output is correct
28 Correct 53 ms 100044 KB Output is correct
29 Correct 67 ms 100176 KB Output is correct
30 Correct 55 ms 100008 KB Output is correct
31 Correct 58 ms 99992 KB Output is correct
32 Correct 57 ms 100092 KB Output is correct
33 Correct 84 ms 100160 KB Output is correct
34 Correct 84 ms 100212 KB Output is correct
35 Correct 80 ms 100872 KB Output is correct
36 Correct 55 ms 99776 KB Output is correct
37 Correct 92 ms 101368 KB Output is correct
38 Correct 87 ms 101572 KB Output is correct
39 Correct 87 ms 101556 KB Output is correct
40 Correct 91 ms 101608 KB Output is correct
41 Correct 111 ms 101580 KB Output is correct
42 Correct 52 ms 100576 KB Output is correct
43 Correct 53 ms 100580 KB Output is correct
44 Correct 52 ms 100540 KB Output is correct
45 Correct 142 ms 103244 KB Output is correct
46 Correct 141 ms 103240 KB Output is correct
47 Correct 226 ms 110028 KB Output is correct
48 Correct 62 ms 113252 KB Output is correct
49 Correct 62 ms 114216 KB Output is correct
50 Correct 73 ms 115232 KB Output is correct
51 Correct 150 ms 118552 KB Output is correct
52 Correct 160 ms 118452 KB Output is correct
53 Correct 83 ms 116428 KB Output is correct
54 Correct 63 ms 115384 KB Output is correct
55 Correct 67 ms 115388 KB Output is correct
56 Correct 72 ms 116520 KB Output is correct
57 Correct 222 ms 115572 KB Output is correct
58 Correct 78 ms 115916 KB Output is correct
59 Correct 89 ms 115948 KB Output is correct
60 Correct 91 ms 116044 KB Output is correct
61 Correct 87 ms 115940 KB Output is correct
62 Correct 165 ms 118220 KB Output is correct
63 Correct 155 ms 134420 KB Output is correct
64 Correct 169 ms 140760 KB Output is correct
65 Correct 472 ms 141212 KB Output is correct
66 Execution timed out 1082 ms 145280 KB Time limit exceeded
67 Halted 0 ms 0 KB -