Submission #709914

#	Time	Username	Problem	Language	Result	Execution time	Memory
709914		noedit	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1096 ms	246468 KiB

skyscraper

#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];
vector<short> sm[MAXN];
vector<short> bg[MAXN];

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);
            bg[d[i].first].push_back(d[i].second);
        }
        else
        {
            sm[d[i].first].push_back(d[i].second);
        }
    }
    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& mv : bg[pos])
        {
            for (int j = pos, k = 0; j < n; j += mv, k++)
            {
                if (dist[j][0] > dst + k)
                {
                    dist[j][0] = dst + k;
                    st.push({-dist[j][0], j, 0});
                }
            }
            for (int j = pos, k = 0; j >= 0; j -= mv, k++)
            {
                if (dist[j][0] > dst + k)
                {
                    dist[j][0] = dst + k;
                    st.push({-dist[j][0], j, 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.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 (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50: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]
   50 |         g[d[i].first][0].push_back({d[i].first, d[i].second, 0});
skyscraper.cpp:50: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]
   50 |         g[d[i].first][0].push_back({d[i].first, d[i].second, 0});

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43