Submission #1133274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133274		g4yuhg	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	10 / 100	8 ms	12192 KiB

skyscraper

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define int long long
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 6
#define N 500005
using namespace std;
ll n, m;
ll b[N], p[N];
ll d[N];
vector<ll> vt[N];
ll ed;
void dij() {
    for (int i = 0; i < n; i ++) {
        d[i] = inf;
    }
    d[0] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 0});
    while (pq.size()) {
        auto u = pq.top().se;
        auto c = pq.top().fi;
        pq.pop();
        if (c > d[u]) continue;
        for (auto it : vt[u]) {
            for (int j = 1; u + j * it < n; j ++) {
                ll v = u + j * it;
                if (d[v] > d[u] + j) {
                    d[v] = d[u] + j;
                    pq.push({d[v], v});
                }
            }
            for (int j = 1; u - j * it >= 0; j ++) {
                ll v = u - j * it;
                if (d[v] > d[u] + j) {
                    d[v] = d[u] + j;
                    pq.push({d[v], v});
                }
            }
        }
    }
}
signed main(void) {
    faster;
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> b[i] >> p[i];
        if (i == 2) {
            ed = b[i];
        }
        vt[b[i]].push_back(p[i]);
    }
    dij();
    if (d[ed] == inf) {
        cout << -1;
    }
    else {
        cout << d[ed];
    }
    return 0;
}

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