Submission #946445

#	Time	Username	Problem	Language	Result	Execution time	Memory
946445		raul2008487	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	1116 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;
bool used[sz];
vl pos[sz];
void solve(){
    ll n, m, i, j, c;
    cin >> n >> m;
    map<pair<ll, ll>, ll> mp;
    vl b(m + 1), p(m + 1);
    for(i = 1; i <= m; i++){
        cin >> b[i] >> p[i];
        b[i]++;
        if(mp[mpr(b[i], p[i])]){continue;}
        mp[mpr(b[i], p[i])]++;
        pos[b[i]].pb(p[i]);
    }
    priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
    pq.push({0, b[1]});
    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 == b[2]){
            cout << dtov << endl;
            return ;
        }
        if(used[v]){continue;}
        used[v] = 1;
        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:21:17: warning: unused variable 'j' [-Wunused-variable]
   21 |     ll n, m, i, j, c;
      |                 ^

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