Submission #684134

#	Time	Username	Problem	Language	Result	Execution time	Memory
684134		kusssso	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	623 ms	6860 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 30005;
const ll inf = 1e18;

int n, m;
int b[N], p[N];
ll d[N];
vector<int> power[N];
vector<pair<int, ll>> g[N];

struct kek {
    int u;
    ll du;
    bool operator < (const kek& oth) const {
        return du > oth.du;
    }  
};

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        power[b[i]].push_back(p[i]);
    }
    fill(begin(d), end(d), inf);
    d[b[0]] = 0;
    priority_queue<kek> pq;
    pq.push({b[0], 0});
    
    while (!pq.empty()) {
        auto [u, du] = pq.top(); pq.pop();
        if (d[u] != du) continue;
        
        // if (u == b[1]) {
            // cout << du;
            // return 0;
        // }
//         
        // cerr << "@" << u << '\n';
        
        for (auto& P : power[u]) {
            for (ll v = u + P, w = 1; v < n; v += P, w++) {
                if (d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    pq.push({v, d[v]});
                }
            }
            for (ll v = u - P, w = 1; v >= 0; v -= P, w++) {
                if (d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    pq.push({v, d[v]});
                    // cerr << u << ' ' << v << '\n';
                }
            }
        }
    }
    cout << (d[b[1]] == inf ? -1 : d[b[1]]);
    
    
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:30: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   50 |                     pq.push({v, d[v]});
      |                              ^
skyscraper.cpp:56:30: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   56 |                     pq.push({v, d[v]});
      |                              ^

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