Submission #705154

#	Time	Username	Problem	Language	Result	Execution time	Memory
705154		bebra	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	273 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define dbg(x) cerr << #x << ": " << x << endl;
 
 
const int MAX_N = 30000 + 5;
const ll INF = 1e9;
vector<pair<int, int>> g[MAX_N];
ll dist[MAX_N];
bool used[MAX_N];
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
    int s, t;
    for (int i = 0; i < m; ++i) {
        int v, k;
        cin >> v >> k;
        if (i == 0) {
            s = v;
        }
        if (i == 1) {
            t = v;
        }
        for (int u = v + k; u < n; u += k) {
            g[v].emplace_back(u, (u - v) / k);
        }
        for (int u = v - k; u >= 0; u -= k) {
            g[v].emplace_back(u, (v - u) / k);
        }
    }

    // maybe lazy edges?
 
    fill_n(dist, n, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [curr_dist, v] = pq.top();
        pq.pop();
        if (used[v]) continue;

        used[v] = true;
        dist[v] = curr_dist;
        if (v == t) break;
        if (dist[v] == INF) break;
        
        for (const auto& [u, w] : g[v]) {
            if (used[u]) continue;
            if (dist[u] <= curr_dist + w) continue;
            dist[u] = curr_dist + w;
            pq.emplace(dist[u], u);
        }
    }
 
    if (!used[t]) {
        cout << "-1\n";
    } else {
        cout << dist[t] << '\n';
    }
 
    return 0;
}
 
 
/*
5 3
0 2
1 1
4 1
*/

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:51:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         if (v == t) break;
      |         ^~

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