oj.uz

Submission #709903

# Submission time Handle Problem Language Result Execution time Memory
709903 2023-03-14T19:03:01 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 458 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 = 300;
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 104 ms 211592 KB Output is correct
2 Correct 109 ms 211688 KB Output is correct
3 Correct 102 ms 211672 KB Output is correct
4 Correct 96 ms 211696 KB Output is correct
5 Correct 96 ms 211648 KB Output is correct
6 Correct 99 ms 211652 KB Output is correct
7 Correct 112 ms 211668 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 211664 KB Output is correct
2 Correct 94 ms 211592 KB Output is correct
3 Correct 96 ms 211692 KB Output is correct
4 Correct 112 ms 211636 KB Output is correct
5 Correct 99 ms 211668 KB Output is correct
6 Correct 95 ms 211660 KB Output is correct
7 Correct 96 ms 211640 KB Output is correct
8 Correct 98 ms 211684 KB Output is correct
9 Correct 97 ms 211788 KB Output is correct
10 Correct 104 ms 211836 KB Output is correct
11 Correct 97 ms 211868 KB Output is correct
12 Correct 97 ms 211808 KB Output is correct
13 Correct 103 ms 211740 KB Output is correct
14 Correct 98 ms 211900 KB Output is correct
15 Correct 99 ms 212068 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 211636 KB Output is correct
2 Correct 97 ms 211608 KB Output is correct
3 Correct 98 ms 211660 KB Output is correct
4 Correct 94 ms 211684 KB Output is correct
5 Correct 93 ms 211700 KB Output is correct
6 Correct 96 ms 211624 KB Output is correct
7 Correct 106 ms 211700 KB Output is correct
8 Correct 95 ms 211612 KB Output is correct
9 Correct 96 ms 211732 KB Output is correct
10 Correct 98 ms 211836 KB Output is correct
11 Correct 104 ms 211828 KB Output is correct
12 Correct 105 ms 211792 KB Output is correct
13 Correct 101 ms 211800 KB Output is correct
14 Correct 98 ms 211876 KB Output is correct
15 Correct 99 ms 211872 KB Output is correct
16 Correct 106 ms 211848 KB Output is correct
17 Correct 127 ms 212680 KB Output is correct
18 Correct 99 ms 213680 KB Output is correct
19 Correct 98 ms 214072 KB Output is correct
20 Correct 98 ms 214124 KB Output is correct
21 Correct 106 ms 212092 KB Output is correct
22 Correct 104 ms 213828 KB Output is correct
23 Correct 100 ms 213620 KB Output is correct
24 Correct 109 ms 214020 KB Output is correct
25 Correct 107 ms 214080 KB Output is correct
26 Correct 99 ms 214016 KB Output is correct
27 Correct 109 ms 214092 KB Output is correct
28 Correct 104 ms 214144 KB Output is correct
29 Correct 132 ms 214208 KB Output is correct
30 Correct 114 ms 214056 KB Output is correct
31 Correct 105 ms 213996 KB Output is correct
32 Correct 105 ms 213964 KB Output is correct
33 Correct 139 ms 214160 KB Output is correct
34 Correct 132 ms 214320 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 211660 KB Output is correct
2 Correct 96 ms 211684 KB Output is correct
3 Correct 110 ms 211692 KB Output is correct
4 Correct 103 ms 211740 KB Output is correct
5 Correct 95 ms 211696 KB Output is correct
6 Correct 99 ms 211648 KB Output is correct
7 Correct 103 ms 211632 KB Output is correct
8 Correct 97 ms 211736 KB Output is correct
9 Correct 98 ms 211760 KB Output is correct
10 Correct 99 ms 211808 KB Output is correct
11 Correct 100 ms 211872 KB Output is correct
12 Correct 101 ms 211816 KB Output is correct
13 Correct 97 ms 211752 KB Output is correct
14 Correct 99 ms 211868 KB Output is correct
15 Correct 98 ms 211976 KB Output is correct
16 Correct 99 ms 211928 KB Output is correct
17 Correct 104 ms 212700 KB Output is correct
18 Correct 99 ms 213808 KB Output is correct
19 Correct 96 ms 214076 KB Output is correct
20 Correct 100 ms 214120 KB Output is correct
21 Correct 96 ms 212092 KB Output is correct
22 Correct 98 ms 213812 KB Output is correct
23 Correct 99 ms 213524 KB Output is correct
24 Correct 112 ms 214048 KB Output is correct
25 Correct 108 ms 214024 KB Output is correct
26 Correct 107 ms 213968 KB Output is correct
27 Correct 102 ms 214064 KB Output is correct
28 Correct 103 ms 214140 KB Output is correct
29 Correct 131 ms 214092 KB Output is correct
30 Correct 106 ms 213964 KB Output is correct
31 Correct 111 ms 214060 KB Output is correct
32 Correct 102 ms 214084 KB Output is correct
33 Correct 142 ms 214216 KB Output is correct
34 Correct 133 ms 214096 KB Output is correct
35 Correct 123 ms 214508 KB Output is correct
36 Correct 100 ms 213092 KB Output is correct
37 Correct 149 ms 215372 KB Output is correct
38 Correct 150 ms 215588 KB Output is correct
39 Correct 138 ms 215672 KB Output is correct
40 Correct 142 ms 215672 KB Output is correct
41 Correct 159 ms 215660 KB Output is correct
42 Correct 106 ms 214540 KB Output is correct
43 Correct 105 ms 214588 KB Output is correct
44 Correct 111 ms 214628 KB Output is correct
45 Correct 281 ms 216492 KB Output is correct
46 Correct 298 ms 216448 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 211624 KB Output is correct
2 Correct 116 ms 211688 KB Output is correct
3 Correct 123 ms 211600 KB Output is correct
4 Correct 125 ms 211688 KB Output is correct
5 Correct 125 ms 211696 KB Output is correct
6 Correct 128 ms 211616 KB Output is correct
7 Correct 126 ms 211676 KB Output is correct
8 Correct 100 ms 211632 KB Output is correct
9 Correct 96 ms 211696 KB Output is correct
10 Correct 98 ms 211720 KB Output is correct
11 Correct 99 ms 211844 KB Output is correct
12 Correct 104 ms 211732 KB Output is correct
13 Correct 105 ms 211832 KB Output is correct
14 Correct 118 ms 211848 KB Output is correct
15 Correct 111 ms 211880 KB Output is correct
16 Correct 93 ms 211864 KB Output is correct
17 Correct 100 ms 212704 KB Output is correct
18 Correct 98 ms 213684 KB Output is correct
19 Correct 99 ms 213960 KB Output is correct
20 Correct 101 ms 214128 KB Output is correct
21 Correct 98 ms 212196 KB Output is correct
22 Correct 101 ms 213816 KB Output is correct
23 Correct 100 ms 213616 KB Output is correct
24 Correct 117 ms 214044 KB Output is correct
25 Correct 97 ms 214088 KB Output is correct
26 Correct 100 ms 213964 KB Output is correct
27 Correct 106 ms 214220 KB Output is correct
28 Correct 103 ms 214060 KB Output is correct
29 Correct 116 ms 214092 KB Output is correct
30 Correct 104 ms 214064 KB Output is correct
31 Correct 107 ms 214092 KB Output is correct
32 Correct 108 ms 214172 KB Output is correct
33 Correct 129 ms 214160 KB Output is correct
34 Correct 132 ms 214092 KB Output is correct
35 Correct 142 ms 214604 KB Output is correct
36 Correct 123 ms 213196 KB Output is correct
37 Correct 154 ms 215556 KB Output is correct
38 Correct 147 ms 215544 KB Output is correct
39 Correct 147 ms 215628 KB Output is correct
40 Correct 146 ms 215628 KB Output is correct
41 Correct 142 ms 215592 KB Output is correct
42 Correct 112 ms 214552 KB Output is correct
43 Correct 114 ms 214548 KB Output is correct
44 Correct 101 ms 214604 KB Output is correct
45 Correct 263 ms 216448 KB Output is correct
46 Correct 264 ms 216456 KB Output is correct
47 Correct 344 ms 229720 KB Output is correct
48 Correct 121 ms 240316 KB Output is correct
49 Correct 117 ms 242776 KB Output is correct
50 Correct 114 ms 245428 KB Output is correct
51 Correct 228 ms 249660 KB Output is correct
52 Correct 227 ms 249704 KB Output is correct
53 Correct 147 ms 247904 KB Output is correct
54 Correct 124 ms 246808 KB Output is correct
55 Correct 122 ms 246912 KB Output is correct
56 Correct 131 ms 248060 KB Output is correct
57 Correct 293 ms 247060 KB Output is correct
58 Correct 140 ms 247432 KB Output is correct
59 Correct 146 ms 247408 KB Output is correct
60 Correct 154 ms 247456 KB Output is correct
61 Correct 178 ms 247448 KB Output is correct
62 Correct 228 ms 249556 KB Output is correct
63 Correct 458 ms 261472 KB Output is correct
64 Runtime error 119 ms 262144 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -