oj.uz

Submission #709902

# Submission time Handle Problem Language Result Execution time Memory
709902 2023-03-14T19:02:11 Z noedit Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 165196 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 = 170;
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 59 ms 120012 KB Output is correct
2 Correct 60 ms 120036 KB Output is correct
3 Correct 55 ms 120084 KB Output is correct
4 Correct 55 ms 120012 KB Output is correct
5 Correct 65 ms 119980 KB Output is correct
6 Correct 52 ms 120016 KB Output is correct
7 Correct 60 ms 120048 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 120036 KB Output is correct
2 Correct 57 ms 120020 KB Output is correct
3 Correct 55 ms 120080 KB Output is correct
4 Correct 55 ms 120008 KB Output is correct
5 Correct 56 ms 120096 KB Output is correct
6 Correct 55 ms 120100 KB Output is correct
7 Correct 55 ms 120012 KB Output is correct
8 Correct 54 ms 120120 KB Output is correct
9 Correct 58 ms 120116 KB Output is correct
10 Correct 56 ms 120080 KB Output is correct
11 Correct 58 ms 120204 KB Output is correct
12 Correct 60 ms 120200 KB Output is correct
13 Correct 56 ms 120140 KB Output is correct
14 Correct 62 ms 120204 KB Output is correct
15 Correct 61 ms 120260 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 120004 KB Output is correct
2 Correct 67 ms 120012 KB Output is correct
3 Correct 66 ms 120060 KB Output is correct
4 Correct 60 ms 120004 KB Output is correct
5 Correct 57 ms 120068 KB Output is correct
6 Correct 56 ms 120228 KB Output is correct
7 Correct 56 ms 120100 KB Output is correct
8 Correct 57 ms 120120 KB Output is correct
9 Correct 56 ms 120096 KB Output is correct
10 Correct 55 ms 120104 KB Output is correct
11 Correct 57 ms 120248 KB Output is correct
12 Correct 58 ms 120200 KB Output is correct
13 Correct 58 ms 120216 KB Output is correct
14 Correct 59 ms 120216 KB Output is correct
15 Correct 60 ms 120220 KB Output is correct
16 Correct 58 ms 120248 KB Output is correct
17 Correct 59 ms 120644 KB Output is correct
18 Correct 56 ms 121304 KB Output is correct
19 Correct 59 ms 121560 KB Output is correct
20 Correct 60 ms 121524 KB Output is correct
21 Correct 66 ms 120392 KB Output is correct
22 Correct 58 ms 121252 KB Output is correct
23 Correct 60 ms 121172 KB Output is correct
24 Correct 60 ms 121356 KB Output is correct
25 Correct 56 ms 121492 KB Output is correct
26 Correct 57 ms 121432 KB Output is correct
27 Correct 58 ms 121516 KB Output is correct
28 Correct 64 ms 121420 KB Output is correct
29 Correct 72 ms 121404 KB Output is correct
30 Correct 61 ms 121324 KB Output is correct
31 Correct 66 ms 121420 KB Output is correct
32 Correct 64 ms 121428 KB Output is correct
33 Correct 97 ms 121472 KB Output is correct
34 Correct 93 ms 121584 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120084 KB Output is correct
2 Correct 58 ms 119980 KB Output is correct
3 Correct 56 ms 120028 KB Output is correct
4 Correct 57 ms 119996 KB Output is correct
5 Correct 66 ms 120072 KB Output is correct
6 Correct 65 ms 120080 KB Output is correct
7 Correct 56 ms 120100 KB Output is correct
8 Correct 56 ms 120012 KB Output is correct
9 Correct 58 ms 120056 KB Output is correct
10 Correct 59 ms 120180 KB Output is correct
11 Correct 59 ms 120140 KB Output is correct
12 Correct 61 ms 120204 KB Output is correct
13 Correct 57 ms 120088 KB Output is correct
14 Correct 58 ms 120224 KB Output is correct
15 Correct 59 ms 120252 KB Output is correct
16 Correct 57 ms 120176 KB Output is correct
17 Correct 62 ms 120680 KB Output is correct
18 Correct 57 ms 121292 KB Output is correct
19 Correct 57 ms 121456 KB Output is correct
20 Correct 57 ms 121556 KB Output is correct
21 Correct 60 ms 120420 KB Output is correct
22 Correct 60 ms 121312 KB Output is correct
23 Correct 60 ms 121164 KB Output is correct
24 Correct 62 ms 121420 KB Output is correct
25 Correct 60 ms 121476 KB Output is correct
26 Correct 59 ms 121420 KB Output is correct
27 Correct 61 ms 121480 KB Output is correct
28 Correct 62 ms 121532 KB Output is correct
29 Correct 88 ms 121420 KB Output is correct
30 Correct 62 ms 121408 KB Output is correct
31 Correct 74 ms 121376 KB Output is correct
32 Correct 62 ms 121344 KB Output is correct
33 Correct 89 ms 121588 KB Output is correct
34 Correct 95 ms 121516 KB Output is correct
35 Correct 80 ms 122184 KB Output is correct
36 Correct 62 ms 120988 KB Output is correct
37 Correct 100 ms 122812 KB Output is correct
38 Correct 104 ms 122968 KB Output is correct
39 Correct 101 ms 122960 KB Output is correct
40 Correct 95 ms 123040 KB Output is correct
41 Correct 104 ms 122952 KB Output is correct
42 Correct 68 ms 121964 KB Output is correct
43 Correct 73 ms 121956 KB Output is correct
44 Correct 68 ms 121952 KB Output is correct
45 Correct 168 ms 124060 KB Output is correct
46 Correct 169 ms 124068 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120012 KB Output is correct
2 Correct 61 ms 120108 KB Output is correct
3 Correct 58 ms 120072 KB Output is correct
4 Correct 62 ms 120024 KB Output is correct
5 Correct 57 ms 120076 KB Output is correct
6 Correct 57 ms 120096 KB Output is correct
7 Correct 56 ms 120008 KB Output is correct
8 Correct 57 ms 119992 KB Output is correct
9 Correct 67 ms 120012 KB Output is correct
10 Correct 60 ms 120068 KB Output is correct
11 Correct 58 ms 120260 KB Output is correct
12 Correct 56 ms 120204 KB Output is correct
13 Correct 57 ms 120128 KB Output is correct
14 Correct 60 ms 120212 KB Output is correct
15 Correct 61 ms 120276 KB Output is correct
16 Correct 57 ms 120284 KB Output is correct
17 Correct 63 ms 120652 KB Output is correct
18 Correct 56 ms 121300 KB Output is correct
19 Correct 57 ms 121340 KB Output is correct
20 Correct 58 ms 121448 KB Output is correct
21 Correct 66 ms 120396 KB Output is correct
22 Correct 58 ms 121292 KB Output is correct
23 Correct 59 ms 121120 KB Output is correct
24 Correct 63 ms 121416 KB Output is correct
25 Correct 60 ms 121460 KB Output is correct
26 Correct 61 ms 121464 KB Output is correct
27 Correct 60 ms 121420 KB Output is correct
28 Correct 62 ms 121420 KB Output is correct
29 Correct 78 ms 121424 KB Output is correct
30 Correct 63 ms 121328 KB Output is correct
31 Correct 69 ms 121468 KB Output is correct
32 Correct 64 ms 121464 KB Output is correct
33 Correct 96 ms 121476 KB Output is correct
34 Correct 93 ms 121588 KB Output is correct
35 Correct 88 ms 122224 KB Output is correct
36 Correct 70 ms 121036 KB Output is correct
37 Correct 103 ms 122768 KB Output is correct
38 Correct 103 ms 123020 KB Output is correct
39 Correct 97 ms 122912 KB Output is correct
40 Correct 100 ms 122920 KB Output is correct
41 Correct 114 ms 122944 KB Output is correct
42 Correct 74 ms 121956 KB Output is correct
43 Correct 72 ms 121988 KB Output is correct
44 Correct 71 ms 121932 KB Output is correct
45 Correct 233 ms 124144 KB Output is correct
46 Correct 209 ms 124156 KB Output is correct
47 Correct 292 ms 132468 KB Output is correct
48 Correct 82 ms 137032 KB Output is correct
49 Correct 88 ms 138276 KB Output is correct
50 Correct 72 ms 139640 KB Output is correct
51 Correct 160 ms 143000 KB Output is correct
52 Correct 178 ms 143032 KB Output is correct
53 Correct 99 ms 141088 KB Output is correct
54 Correct 81 ms 139984 KB Output is correct
55 Correct 78 ms 139956 KB Output is correct
56 Correct 85 ms 141176 KB Output is correct
57 Correct 246 ms 140304 KB Output is correct
58 Correct 90 ms 140608 KB Output is correct
59 Correct 100 ms 140560 KB Output is correct
60 Correct 112 ms 140724 KB Output is correct
61 Correct 96 ms 140672 KB Output is correct
62 Correct 169 ms 142832 KB Output is correct
63 Correct 162 ms 158884 KB Output is correct
64 Correct 190 ms 165196 KB Output is correct
65 Correct 715 ms 163700 KB Output is correct
66 Execution timed out 1091 ms 159972 KB Time limit exceeded
67 Halted 0 ms 0 KB -