Submission #666526

#	Time	Username	Problem	Language	Result	Execution time	Memory
666526		Farbod	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	675 ms	3820 KiB

skyscraper

#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int N = 30005, inf = 1e9;

int n, m, x[N];
vector <int> v[N];

int d[N];
set <pair <int, int>> q;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int p;
        cin >> x[i] >> p, v[x[i]].push_back(p);
    }

    int tmp = x[1];
    for (int i = 0; i < n; i++)
        d[i] = inf;

    d[x[0]] = 0, q.insert({0, x[0]});
    while (q.size()) {
        int x = q.begin() -> second;
        q.erase(q.begin());

        if (x == tmp)
            return cout << d[x], 0;

        for (int i = 0; i < v[x].size(); i++) {
            int j = v[x][i];
            for (int k = 1; x + k * j < n; k++)
                if (d[x] + k < d[x + k * j])
                    q.erase({d[x + k * j], x + k * j}),
                    d[x + k * j] = d[x] + k,
                    q.insert({d[x + k * j], x + k * j});
            for (int k = 1; x - k * j >= 0; k++)
                if (d[x] + k < d[x - k * j])
                    q.erase({d[x - k * j], x - k * j}),
                    d[x - k * j] = d[x] + k,
                    q.insert({d[x - k * j], x - k * j});
        }
    }

    cout << -1;

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < v[x].size(); i++) {
      |                         ~~^~~~~~~~~~~~~

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