Submission #709913

# Submission time Handle Problem Language Result Execution time Memory
709913 2023-03-14T19:22:55 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
1000 ms 259840 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 = 295;
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 (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});
        }
    }
    priority_queue<array<int, 3> > st;
    st.push({0, d[0].first, 0});
    dist[d[0].first][0] = 0;
    while (!st.empty())
    {
        auto [dst, pos, pw] = st.top();
        dst = -dst;
        st.pop();
        if (dst > dist[pos][pw]) continue;
        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.push({-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.push({-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.push({-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.push({-dist[pos + pw][0], pos + pw, 0});
                }
            }
            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.push({-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:49:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   49 |             g[d[i].first][0].push_back({j, 0, k});
      |                                         ^
skyscraper.cpp:49:47: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
   49 |             g[d[i].first][0].push_back({j, 0, k});
      |                                               ^
skyscraper.cpp:53:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   53 |             g[d[i].first][0].push_back({j, 0, k});
      |                                         ^
skyscraper.cpp:53:47: warning: narrowing conversion of 'k' from 'int' to 'short int' [-Wnarrowing]
   53 |             g[d[i].first][0].push_back({j, 0, k});
      |                                               ^
# Verdict Execution time Memory Grader output
1 Correct 95 ms 208168 KB Output is correct
2 Correct 104 ms 208092 KB Output is correct
3 Correct 105 ms 208092 KB Output is correct
4 Correct 121 ms 208080 KB Output is correct
5 Correct 101 ms 208148 KB Output is correct
6 Correct 97 ms 208276 KB Output is correct
7 Correct 94 ms 208076 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 108 ms 208124 KB Output is correct
2 Correct 106 ms 208072 KB Output is correct
3 Correct 94 ms 208180 KB Output is correct
4 Correct 93 ms 208112 KB Output is correct
5 Correct 93 ms 208180 KB Output is correct
6 Correct 104 ms 208076 KB Output is correct
7 Correct 114 ms 208076 KB Output is correct
8 Correct 92 ms 208144 KB Output is correct
9 Correct 95 ms 208232 KB Output is correct
10 Correct 93 ms 208200 KB Output is correct
11 Correct 101 ms 208380 KB Output is correct
12 Correct 93 ms 208272 KB Output is correct
13 Correct 95 ms 208328 KB Output is correct
14 Correct 98 ms 208316 KB Output is correct
15 Correct 100 ms 208320 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 130 ms 208136 KB Output is correct
2 Correct 97 ms 208112 KB Output is correct
3 Correct 101 ms 208100 KB Output is correct
4 Correct 97 ms 208160 KB Output is correct
5 Correct 96 ms 208172 KB Output is correct
6 Correct 99 ms 208292 KB Output is correct
7 Correct 97 ms 208060 KB Output is correct
8 Correct 103 ms 208132 KB Output is correct
9 Correct 105 ms 208152 KB Output is correct
10 Correct 95 ms 208212 KB Output is correct
11 Correct 99 ms 208332 KB Output is correct
12 Correct 97 ms 208332 KB Output is correct
13 Correct 103 ms 208288 KB Output is correct
14 Correct 97 ms 208328 KB Output is correct
15 Correct 96 ms 208336 KB Output is correct
16 Correct 103 ms 208308 KB Output is correct
17 Correct 99 ms 209016 KB Output is correct
18 Correct 100 ms 210224 KB Output is correct
19 Correct 98 ms 210476 KB Output is correct
20 Correct 99 ms 210512 KB Output is correct
21 Correct 93 ms 208588 KB Output is correct
22 Correct 104 ms 210148 KB Output is correct
23 Correct 114 ms 210040 KB Output is correct
24 Correct 95 ms 210460 KB Output is correct
25 Correct 96 ms 210480 KB Output is correct
26 Correct 98 ms 210424 KB Output is correct
27 Correct 110 ms 210512 KB Output is correct
28 Correct 96 ms 210556 KB Output is correct
29 Correct 100 ms 210464 KB Output is correct
30 Correct 102 ms 210464 KB Output is correct
31 Correct 97 ms 210432 KB Output is correct
32 Correct 96 ms 210436 KB Output is correct
33 Correct 107 ms 210592 KB Output is correct
34 Correct 107 ms 210592 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 97 ms 208156 KB Output is correct
2 Correct 93 ms 208076 KB Output is correct
3 Correct 100 ms 208088 KB Output is correct
4 Correct 94 ms 208124 KB Output is correct
5 Correct 114 ms 208064 KB Output is correct
6 Correct 96 ms 208060 KB Output is correct
7 Correct 93 ms 208060 KB Output is correct
8 Correct 97 ms 208116 KB Output is correct
9 Correct 100 ms 208144 KB Output is correct
10 Correct 101 ms 208296 KB Output is correct
11 Correct 101 ms 208304 KB Output is correct
12 Correct 98 ms 208252 KB Output is correct
13 Correct 98 ms 208344 KB Output is correct
14 Correct 94 ms 208484 KB Output is correct
15 Correct 97 ms 208304 KB Output is correct
16 Correct 105 ms 208344 KB Output is correct
17 Correct 116 ms 209132 KB Output is correct
18 Correct 121 ms 210228 KB Output is correct
19 Correct 111 ms 210488 KB Output is correct
20 Correct 112 ms 210508 KB Output is correct
21 Correct 123 ms 208688 KB Output is correct
22 Correct 123 ms 210240 KB Output is correct
23 Correct 96 ms 209992 KB Output is correct
24 Correct 102 ms 210344 KB Output is correct
25 Correct 106 ms 210564 KB Output is correct
26 Correct 99 ms 210460 KB Output is correct
27 Correct 101 ms 210612 KB Output is correct
28 Correct 100 ms 210520 KB Output is correct
29 Correct 101 ms 210508 KB Output is correct
30 Correct 99 ms 210444 KB Output is correct
31 Correct 95 ms 210496 KB Output is correct
32 Correct 111 ms 210516 KB Output is correct
33 Correct 106 ms 210596 KB Output is correct
34 Correct 109 ms 210508 KB Output is correct
35 Correct 115 ms 210828 KB Output is correct
36 Correct 105 ms 209596 KB Output is correct
37 Correct 116 ms 211544 KB Output is correct
38 Correct 126 ms 211784 KB Output is correct
39 Correct 113 ms 211864 KB Output is correct
40 Correct 112 ms 211904 KB Output is correct
41 Correct 116 ms 211956 KB Output is correct
42 Correct 104 ms 210996 KB Output is correct
43 Correct 107 ms 211004 KB Output is correct
44 Correct 104 ms 211020 KB Output is correct
45 Correct 166 ms 211532 KB Output is correct
46 Correct 172 ms 211520 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 99 ms 208168 KB Output is correct
2 Correct 94 ms 208160 KB Output is correct
3 Correct 93 ms 208116 KB Output is correct
4 Correct 95 ms 208152 KB Output is correct
5 Correct 97 ms 208224 KB Output is correct
6 Correct 103 ms 208152 KB Output is correct
7 Correct 97 ms 208072 KB Output is correct
8 Correct 94 ms 208144 KB Output is correct
9 Correct 94 ms 208212 KB Output is correct
10 Correct 102 ms 208292 KB Output is correct
11 Correct 98 ms 208252 KB Output is correct
12 Correct 94 ms 208280 KB Output is correct
13 Correct 95 ms 208312 KB Output is correct
14 Correct 101 ms 208308 KB Output is correct
15 Correct 97 ms 208336 KB Output is correct
16 Correct 93 ms 208296 KB Output is correct
17 Correct 101 ms 209044 KB Output is correct
18 Correct 119 ms 210120 KB Output is correct
19 Correct 98 ms 210508 KB Output is correct
20 Correct 98 ms 210508 KB Output is correct
21 Correct 97 ms 208664 KB Output is correct
22 Correct 95 ms 210260 KB Output is correct
23 Correct 106 ms 210064 KB Output is correct
24 Correct 98 ms 210352 KB Output is correct
25 Correct 100 ms 210548 KB Output is correct
26 Correct 104 ms 210524 KB Output is correct
27 Correct 108 ms 210448 KB Output is correct
28 Correct 99 ms 210560 KB Output is correct
29 Correct 111 ms 210516 KB Output is correct
30 Correct 96 ms 210480 KB Output is correct
31 Correct 99 ms 210420 KB Output is correct
32 Correct 102 ms 210488 KB Output is correct
33 Correct 108 ms 210616 KB Output is correct
34 Correct 109 ms 210508 KB Output is correct
35 Correct 111 ms 210892 KB Output is correct
36 Correct 104 ms 209616 KB Output is correct
37 Correct 119 ms 211512 KB Output is correct
38 Correct 129 ms 211796 KB Output is correct
39 Correct 116 ms 211812 KB Output is correct
40 Correct 120 ms 211800 KB Output is correct
41 Correct 118 ms 211816 KB Output is correct
42 Correct 101 ms 211040 KB Output is correct
43 Correct 103 ms 211012 KB Output is correct
44 Correct 113 ms 211052 KB Output is correct
45 Correct 167 ms 211528 KB Output is correct
46 Correct 169 ms 211528 KB Output is correct
47 Correct 192 ms 225844 KB Output is correct
48 Correct 113 ms 236420 KB Output is correct
49 Correct 113 ms 238776 KB Output is correct
50 Correct 112 ms 241240 KB Output is correct
51 Correct 153 ms 245352 KB Output is correct
52 Correct 197 ms 245240 KB Output is correct
53 Correct 128 ms 243864 KB Output is correct
54 Correct 109 ms 242784 KB Output is correct
55 Correct 113 ms 242804 KB Output is correct
56 Correct 126 ms 243916 KB Output is correct
57 Correct 183 ms 242848 KB Output is correct
58 Correct 117 ms 243324 KB Output is correct
59 Correct 126 ms 243296 KB Output is correct
60 Correct 137 ms 243316 KB Output is correct
61 Correct 125 ms 243424 KB Output is correct
62 Correct 164 ms 245384 KB Output is correct
63 Correct 268 ms 258736 KB Output is correct
64 Correct 338 ms 259840 KB Output is correct
65 Correct 796 ms 252532 KB Output is correct
66 Execution timed out 1070 ms 243852 KB Time limit exceeded
67 Halted 0 ms 0 KB -