oj.uz

Submission #709910

# Submission time Handle Problem Language Result Execution time Memory
709910 2023-03-14T19:11:07 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 255228 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 = 290;
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)
            {
                if (dist[pos - pw][pw] > dst + 1)
                {
                    st.erase({dist[pos - pw][pw], pos - pw, pw});
                    dist[pos - pw][pw] = dst + 1;
                    st.insert({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.insert({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.insert({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.insert({dist[pos + pw][0], pos + pw, 0});
                }
            }
        }
        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});
      |                                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 204636 KB Output is correct
2 Correct 95 ms 204532 KB Output is correct
3 Correct 91 ms 204592 KB Output is correct
4 Correct 93 ms 204604 KB Output is correct
5 Correct 95 ms 204708 KB Output is correct
6 Correct 95 ms 204816 KB Output is correct
7 Correct 95 ms 204620 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 204648 KB Output is correct
2 Correct 90 ms 204560 KB Output is correct
3 Correct 105 ms 204596 KB Output is correct
4 Correct 114 ms 204528 KB Output is correct
5 Correct 100 ms 204608 KB Output is correct
6 Correct 97 ms 204588 KB Output is correct
7 Correct 95 ms 204664 KB Output is correct
8 Correct 98 ms 204696 KB Output is correct
9 Correct 98 ms 204724 KB Output is correct
10 Correct 93 ms 204696 KB Output is correct
11 Correct 94 ms 204864 KB Output is correct
12 Correct 95 ms 204748 KB Output is correct
13 Correct 103 ms 204748 KB Output is correct
14 Correct 98 ms 204872 KB Output is correct
15 Correct 96 ms 204916 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 204640 KB Output is correct
2 Correct 96 ms 204608 KB Output is correct
3 Correct 97 ms 204552 KB Output is correct
4 Correct 99 ms 204568 KB Output is correct
5 Correct 92 ms 204672 KB Output is correct
6 Correct 92 ms 204600 KB Output is correct
7 Correct 93 ms 204616 KB Output is correct
8 Correct 93 ms 204688 KB Output is correct
9 Correct 102 ms 204628 KB Output is correct
10 Correct 107 ms 204756 KB Output is correct
11 Correct 106 ms 204856 KB Output is correct
12 Correct 95 ms 204752 KB Output is correct
13 Correct 97 ms 204760 KB Output is correct
14 Correct 107 ms 204868 KB Output is correct
15 Correct 98 ms 205040 KB Output is correct
16 Correct 95 ms 204836 KB Output is correct
17 Correct 99 ms 205632 KB Output is correct
18 Correct 94 ms 206668 KB Output is correct
19 Correct 94 ms 206904 KB Output is correct
20 Correct 97 ms 207004 KB Output is correct
21 Correct 100 ms 205132 KB Output is correct
22 Correct 104 ms 206760 KB Output is correct
23 Correct 96 ms 206412 KB Output is correct
24 Correct 100 ms 206800 KB Output is correct
25 Correct 97 ms 206908 KB Output is correct
26 Correct 98 ms 206844 KB Output is correct
27 Correct 96 ms 206928 KB Output is correct
28 Correct 101 ms 206972 KB Output is correct
29 Correct 109 ms 206904 KB Output is correct
30 Correct 101 ms 206936 KB Output is correct
31 Correct 101 ms 206872 KB Output is correct
32 Correct 102 ms 206940 KB Output is correct
33 Correct 124 ms 207148 KB Output is correct
34 Correct 120 ms 207084 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 204564 KB Output is correct
2 Correct 93 ms 204760 KB Output is correct
3 Correct 94 ms 204600 KB Output is correct
4 Correct 101 ms 204592 KB Output is correct
5 Correct 105 ms 204652 KB Output is correct
6 Correct 91 ms 204656 KB Output is correct
7 Correct 95 ms 204544 KB Output is correct
8 Correct 96 ms 204680 KB Output is correct
9 Correct 95 ms 204604 KB Output is correct
10 Correct 95 ms 204704 KB Output is correct
11 Correct 95 ms 204876 KB Output is correct
12 Correct 94 ms 204720 KB Output is correct
13 Correct 93 ms 204760 KB Output is correct
14 Correct 105 ms 204808 KB Output is correct
15 Correct 93 ms 204864 KB Output is correct
16 Correct 94 ms 204780 KB Output is correct
17 Correct 98 ms 205636 KB Output is correct
18 Correct 101 ms 206568 KB Output is correct
19 Correct 93 ms 206880 KB Output is correct
20 Correct 108 ms 206924 KB Output is correct
21 Correct 103 ms 205124 KB Output is correct
22 Correct 95 ms 206604 KB Output is correct
23 Correct 101 ms 206536 KB Output is correct
24 Correct 98 ms 206808 KB Output is correct
25 Correct 96 ms 206944 KB Output is correct
26 Correct 95 ms 206944 KB Output is correct
27 Correct 105 ms 206976 KB Output is correct
28 Correct 107 ms 206924 KB Output is correct
29 Correct 110 ms 206924 KB Output is correct
30 Correct 101 ms 206924 KB Output is correct
31 Correct 121 ms 206908 KB Output is correct
32 Correct 105 ms 206900 KB Output is correct
33 Correct 119 ms 206976 KB Output is correct
34 Correct 118 ms 207064 KB Output is correct
35 Correct 118 ms 207488 KB Output is correct
36 Correct 98 ms 206064 KB Output is correct
37 Correct 136 ms 208220 KB Output is correct
38 Correct 129 ms 208444 KB Output is correct
39 Correct 130 ms 208460 KB Output is correct
40 Correct 127 ms 208528 KB Output is correct
41 Correct 130 ms 208516 KB Output is correct
42 Correct 103 ms 207496 KB Output is correct
43 Correct 104 ms 207424 KB Output is correct
44 Correct 98 ms 207500 KB Output is correct
45 Correct 217 ms 209304 KB Output is correct
46 Correct 216 ms 209216 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 204608 KB Output is correct
2 Correct 93 ms 204604 KB Output is correct
3 Correct 101 ms 204556 KB Output is correct
4 Correct 107 ms 204548 KB Output is correct
5 Correct 92 ms 204580 KB Output is correct
6 Correct 97 ms 204656 KB Output is correct
7 Correct 100 ms 204584 KB Output is correct
8 Correct 113 ms 204620 KB Output is correct
9 Correct 104 ms 204608 KB Output is correct
10 Correct 104 ms 204672 KB Output is correct
11 Correct 92 ms 204876 KB Output is correct
12 Correct 95 ms 204740 KB Output is correct
13 Correct 93 ms 204712 KB Output is correct
14 Correct 94 ms 204908 KB Output is correct
15 Correct 98 ms 204876 KB Output is correct
16 Correct 93 ms 204812 KB Output is correct
17 Correct 97 ms 205516 KB Output is correct
18 Correct 97 ms 206636 KB Output is correct
19 Correct 94 ms 206900 KB Output is correct
20 Correct 96 ms 207056 KB Output is correct
21 Correct 96 ms 205072 KB Output is correct
22 Correct 95 ms 206676 KB Output is correct
23 Correct 108 ms 206520 KB Output is correct
24 Correct 101 ms 206912 KB Output is correct
25 Correct 99 ms 206940 KB Output is correct
26 Correct 103 ms 206932 KB Output is correct
27 Correct 104 ms 206964 KB Output is correct
28 Correct 101 ms 206992 KB Output is correct
29 Correct 108 ms 206892 KB Output is correct
30 Correct 100 ms 206856 KB Output is correct
31 Correct 103 ms 206844 KB Output is correct
32 Correct 109 ms 206932 KB Output is correct
33 Correct 127 ms 207080 KB Output is correct
34 Correct 120 ms 207052 KB Output is correct
35 Correct 125 ms 207440 KB Output is correct
36 Correct 99 ms 206124 KB Output is correct
37 Correct 139 ms 208240 KB Output is correct
38 Correct 130 ms 208432 KB Output is correct
39 Correct 131 ms 208536 KB Output is correct
40 Correct 139 ms 208484 KB Output is correct
41 Correct 134 ms 208460 KB Output is correct
42 Correct 99 ms 207432 KB Output is correct
43 Correct 100 ms 207464 KB Output is correct
44 Correct 100 ms 207440 KB Output is correct
45 Correct 227 ms 209232 KB Output is correct
46 Correct 221 ms 209216 KB Output is correct
47 Correct 307 ms 222284 KB Output is correct
48 Correct 119 ms 232420 KB Output is correct
49 Correct 114 ms 234644 KB Output is correct
50 Correct 120 ms 237304 KB Output is correct
51 Correct 204 ms 241464 KB Output is correct
52 Correct 195 ms 241468 KB Output is correct
53 Correct 133 ms 239732 KB Output is correct
54 Correct 113 ms 238908 KB Output is correct
55 Correct 116 ms 238660 KB Output is correct
56 Correct 121 ms 239820 KB Output is correct
57 Correct 261 ms 238740 KB Output is correct
58 Correct 143 ms 239232 KB Output is correct
59 Correct 146 ms 239252 KB Output is correct
60 Correct 162 ms 239184 KB Output is correct
61 Correct 139 ms 239260 KB Output is correct
62 Correct 204 ms 241228 KB Output is correct
63 Correct 361 ms 254040 KB Output is correct
64 Correct 516 ms 255228 KB Output is correct
65 Execution timed out 1087 ms 248836 KB Time limit exceeded
66 Halted 0 ms 0 KB -