oj.uz

Submission #709888

# Submission time Handle Problem Language Result Execution time Memory
709888 2023-03-14T18:36:59 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 242992 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 = 120;
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 41 ms 84832 KB Output is correct
2 Correct 54 ms 84764 KB Output is correct
3 Correct 53 ms 84800 KB Output is correct
4 Correct 49 ms 84828 KB Output is correct
5 Correct 43 ms 84888 KB Output is correct
6 Correct 47 ms 84816 KB Output is correct
7 Correct 46 ms 84848 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 84744 KB Output is correct
2 Correct 51 ms 84864 KB Output is correct
3 Correct 45 ms 84768 KB Output is correct
4 Correct 40 ms 84868 KB Output is correct
5 Correct 45 ms 84884 KB Output is correct
6 Correct 45 ms 84784 KB Output is correct
7 Correct 40 ms 84764 KB Output is correct
8 Correct 46 ms 84792 KB Output is correct
9 Correct 58 ms 84952 KB Output is correct
10 Correct 51 ms 85172 KB Output is correct
11 Correct 56 ms 85204 KB Output is correct
12 Correct 47 ms 85088 KB Output is correct
13 Correct 50 ms 85148 KB Output is correct
14 Correct 59 ms 85308 KB Output is correct
15 Correct 52 ms 85280 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 84880 KB Output is correct
2 Correct 44 ms 84756 KB Output is correct
3 Correct 42 ms 84820 KB Output is correct
4 Correct 43 ms 84800 KB Output is correct
5 Correct 43 ms 84792 KB Output is correct
6 Correct 50 ms 84812 KB Output is correct
7 Correct 42 ms 84836 KB Output is correct
8 Correct 48 ms 84876 KB Output is correct
9 Correct 47 ms 84860 KB Output is correct
10 Correct 45 ms 85100 KB Output is correct
11 Correct 48 ms 85264 KB Output is correct
12 Correct 41 ms 85100 KB Output is correct
13 Correct 48 ms 85172 KB Output is correct
14 Correct 49 ms 85296 KB Output is correct
15 Correct 52 ms 85308 KB Output is correct
16 Correct 44 ms 85612 KB Output is correct
17 Correct 51 ms 88020 KB Output is correct
18 Correct 68 ms 92128 KB Output is correct
19 Correct 82 ms 93212 KB Output is correct
20 Correct 70 ms 93336 KB Output is correct
21 Correct 47 ms 86528 KB Output is correct
22 Correct 75 ms 92364 KB Output is correct
23 Correct 76 ms 91568 KB Output is correct
24 Correct 73 ms 92944 KB Output is correct
25 Correct 69 ms 93348 KB Output is correct
26 Correct 75 ms 93300 KB Output is correct
27 Correct 87 ms 93204 KB Output is correct
28 Correct 90 ms 93256 KB Output is correct
29 Correct 87 ms 93320 KB Output is correct
30 Correct 69 ms 93232 KB Output is correct
31 Correct 78 ms 93208 KB Output is correct
32 Correct 83 ms 93272 KB Output is correct
33 Correct 141 ms 93532 KB Output is correct
34 Correct 102 ms 93416 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 84768 KB Output is correct
2 Correct 41 ms 84776 KB Output is correct
3 Correct 42 ms 84812 KB Output is correct
4 Correct 44 ms 84812 KB Output is correct
5 Correct 45 ms 84836 KB Output is correct
6 Correct 47 ms 84868 KB Output is correct
7 Correct 51 ms 84808 KB Output is correct
8 Correct 41 ms 84812 KB Output is correct
9 Correct 43 ms 84888 KB Output is correct
10 Correct 44 ms 85172 KB Output is correct
11 Correct 52 ms 85252 KB Output is correct
12 Correct 52 ms 85120 KB Output is correct
13 Correct 41 ms 85144 KB Output is correct
14 Correct 44 ms 85204 KB Output is correct
15 Correct 53 ms 85240 KB Output is correct
16 Correct 42 ms 85716 KB Output is correct
17 Correct 62 ms 88012 KB Output is correct
18 Correct 67 ms 92184 KB Output is correct
19 Correct 89 ms 93288 KB Output is correct
20 Correct 70 ms 93256 KB Output is correct
21 Correct 45 ms 86536 KB Output is correct
22 Correct 69 ms 92372 KB Output is correct
23 Correct 71 ms 91636 KB Output is correct
24 Correct 73 ms 92972 KB Output is correct
25 Correct 81 ms 93328 KB Output is correct
26 Correct 73 ms 93300 KB Output is correct
27 Correct 81 ms 93388 KB Output is correct
28 Correct 82 ms 93304 KB Output is correct
29 Correct 86 ms 93276 KB Output is correct
30 Correct 72 ms 93216 KB Output is correct
31 Correct 79 ms 93260 KB Output is correct
32 Correct 87 ms 93280 KB Output is correct
33 Correct 121 ms 93356 KB Output is correct
34 Correct 108 ms 93424 KB Output is correct
35 Correct 86 ms 92068 KB Output is correct
36 Correct 60 ms 89680 KB Output is correct
37 Correct 143 ms 94356 KB Output is correct
38 Correct 126 ms 94768 KB Output is correct
39 Correct 118 ms 94792 KB Output is correct
40 Correct 121 ms 94880 KB Output is correct
41 Correct 115 ms 94796 KB Output is correct
42 Correct 115 ms 93604 KB Output is correct
43 Correct 113 ms 93704 KB Output is correct
44 Correct 112 ms 93664 KB Output is correct
45 Correct 192 ms 96340 KB Output is correct
46 Correct 159 ms 96308 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 84832 KB Output is correct
2 Correct 45 ms 84832 KB Output is correct
3 Correct 47 ms 84844 KB Output is correct
4 Correct 60 ms 84868 KB Output is correct
5 Correct 55 ms 84756 KB Output is correct
6 Correct 54 ms 84812 KB Output is correct
7 Correct 46 ms 84812 KB Output is correct
8 Correct 44 ms 84900 KB Output is correct
9 Correct 46 ms 84960 KB Output is correct
10 Correct 47 ms 85088 KB Output is correct
11 Correct 42 ms 85256 KB Output is correct
12 Correct 50 ms 85108 KB Output is correct
13 Correct 60 ms 85172 KB Output is correct
14 Correct 48 ms 85196 KB Output is correct
15 Correct 46 ms 85248 KB Output is correct
16 Correct 46 ms 85708 KB Output is correct
17 Correct 59 ms 88060 KB Output is correct
18 Correct 75 ms 92176 KB Output is correct
19 Correct 84 ms 93256 KB Output is correct
20 Correct 90 ms 93300 KB Output is correct
21 Correct 60 ms 86532 KB Output is correct
22 Correct 75 ms 92372 KB Output is correct
23 Correct 84 ms 91616 KB Output is correct
24 Correct 86 ms 92932 KB Output is correct
25 Correct 82 ms 93456 KB Output is correct
26 Correct 76 ms 93300 KB Output is correct
27 Correct 86 ms 93216 KB Output is correct
28 Correct 80 ms 93340 KB Output is correct
29 Correct 92 ms 93308 KB Output is correct
30 Correct 80 ms 93272 KB Output is correct
31 Correct 94 ms 93288 KB Output is correct
32 Correct 86 ms 93260 KB Output is correct
33 Correct 112 ms 93388 KB Output is correct
34 Correct 120 ms 93432 KB Output is correct
35 Correct 106 ms 92324 KB Output is correct
36 Correct 72 ms 89736 KB Output is correct
37 Correct 115 ms 94552 KB Output is correct
38 Correct 133 ms 95100 KB Output is correct
39 Correct 115 ms 95040 KB Output is correct
40 Correct 126 ms 95104 KB Output is correct
41 Correct 158 ms 95088 KB Output is correct
42 Correct 102 ms 93776 KB Output is correct
43 Correct 88 ms 93844 KB Output is correct
44 Correct 85 ms 93940 KB Output is correct
45 Correct 162 ms 96524 KB Output is correct
46 Correct 161 ms 96552 KB Output is correct
47 Correct 425 ms 141312 KB Output is correct
48 Correct 401 ms 184024 KB Output is correct
49 Correct 398 ms 192964 KB Output is correct
50 Correct 473 ms 203212 KB Output is correct
51 Correct 590 ms 214156 KB Output is correct
52 Correct 563 ms 214136 KB Output is correct
53 Correct 492 ms 212112 KB Output is correct
54 Correct 482 ms 210688 KB Output is correct
55 Correct 497 ms 210684 KB Output is correct
56 Correct 489 ms 212092 KB Output is correct
57 Correct 704 ms 210904 KB Output is correct
58 Correct 481 ms 211344 KB Output is correct
59 Correct 539 ms 211396 KB Output is correct
60 Correct 587 ms 211700 KB Output is correct
61 Correct 501 ms 211544 KB Output is correct
62 Correct 620 ms 213996 KB Output is correct
63 Correct 656 ms 229768 KB Output is correct
64 Correct 633 ms 235808 KB Output is correct
65 Correct 880 ms 242992 KB Output is correct
66 Execution timed out 1092 ms 241756 KB Time limit exceeded
67 Halted 0 ms 0 KB -