Submission #946427

#	Time	Username	Problem	Language	Result	Execution time	Memory
946427		raul2008487	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1164 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi firp
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 3e4+5;
const ll inf = 100000000000000000;
const ll LG = 26;
vl pos[sz];
void solve(){
    ll n, m, i, j, b, p, c;
    cin >> n >> m;
    for(i = 1; i <= m; i++){
        cin >> b >> p;
        pos[b + 1].pb(p);
    }
    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    pq.push({0ll, 1ll});
    vl dis(n + 1, inf);
    dis[1] = 0;
    while(!pq.empty()){
        ll v = pq.top()[1];
        ll dtov = pq.top()[0];
        pq.pop();
        if(v == 2){
            cout << dtov << endl;
            return ;
        }
        if(dtov != dis[v]){continue;}
        for(auto P: pos[v]){
            c = 1;
            for(i = v + P; i <= n; i += P, c++){
                if(dis[i] > dis[v] + c){
                    dis[i] = dis[v] + c;
                    pq.push({dis[i], i});
                }
            }
            c = 1;
            for(i = v - P; i > 0; i -= P, c++){
                if(dis[i] > dis[v] + c){
                    dis[i] = dis[v] + c;
                    pq.push({dis[i], i});
                }
            }
        }
    }
    cout << -1 << endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    ///cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:20:17: warning: unused variable 'j' [-Wunused-variable]
   20 |     ll n, m, i, j, b, p, c;
      |                 ^

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