Submission #659891

#	Time	Username	Problem	Language	Result	Execution time	Memory
659891		four_specks	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	120 ms	63600 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

void solve()
{
    int n, m;
    cin >> n >> m;

    int s, t;
    vector<vector<int>> doges(n);

    for (int i = 0; i < m; i++)
    {
        int b, p;
        cin >> b >> p;

        if (i == 0)
            s = b;
        else if (i == 1)
            t = b;

        doges[b].push_back(p);
    }

    for (auto &jumps : doges)
    {
        sort(jumps.begin(), jumps.end());
        jumps.erase(unique(jumps.begin(), jumps.end()), jumps.end());
    }

    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < n; i++)
    {
        for (int x : doges[i])
        {
            for (int c = 1; i + c * x < n; c++)
            {
                int j = i + c * x;
                adj[i].emplace_back(j, c);
                if (binary_search(doges[j].begin(), doges[j].end(), x))
                    break;
            }
            for (int c = 1; i - c * x >= 0; c++)
            {
                int j = i - c * x;
                adj[i].emplace_back(j, c);
                if (binary_search(doges[j].begin(), doges[j].end(), x))
                    break;
            }
        }
    }

    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>> pq;
    for (dist[s] = 0, pq.emplace(-dist[s], s); !pq.empty();)
    {
        auto [d, u] = pq.top();
        pq.pop();

        if (-d != dist[u])
            continue;

        for (auto [v, x] : adj[u])
        {
            if (dist[u] + x < dist[v])
                dist[v] = dist[u] + x, pq.emplace(-dist[v], v);
        }
    }

    cout << (dist[t] != INT_MAX ? dist[t] : -1) << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:75:20: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     cout << (dist[t] != INT_MAX ? dist[t] : -1) << '\n';
      |                    ^

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