Submission #1125302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125302		njoop	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	797 ms	305076 KiB

skyscraper

#include <bits/stdc++.h>
#define tiii tuple<int, int, int>
using namespace std;

int MXN = 30000;
int n, m, dis[30010][200], b, p, d=199, st, en;
vector<tiii> g[30010][200];
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;

void dijkstra() {
    pq.push({0, st, 0});
    while(pq.size()) {
        int cd = get<0>(pq.top());
        int cb = get<1>(pq.top());
        int cp = get<2>(pq.top());
        pq.pop();
        if(cd > dis[cb][cp]) continue;
        for(auto i: g[cb][cp]) {
            int nd = cd+get<2>(i);
            int nb = get<0>(i);
            int np = get<1>(i);
            if(nd < dis[nb][np]) {
                dis[nb][np] = nd;
                pq.push({nd, nb, np});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=0; i<sqrt(MXN); i++) {
        for(int j=0; j<n; j++) {
            if(j-i >= 0) {
                g[j-i][i].push_back({j, i, 1});
            }
            if(j+i < n) {
                g[j+i][i].push_back({j, i, 1});
            }
            g[j][i].push_back({j, 0, 0});
        }
    }
    for(int i=0; i<30010; i++) {
        for(int j=0; j<200; j++) {
            dis[i][j] = 1e9;
        }
    }
    for(int i=0; i<m; i++) {
        cin >> b >> p;
        if(i == 0) st = b;
        if(i == 1) en = b;
        if(p >= sqrt(MXN)) {
            int cnt = 0;
            for(int j=b; j<n; j+=p) {
                g[b][d].push_back({j, 0, cnt});
                cnt++;
            }
            cnt = 1;
            for(int j=b-p; j>=0; j-=p) {
                g[b][d].push_back({j, 0, cnt});
                cnt++;
            }
            g[b][0].push_back({b, d, 0});
        } else {
            g[b][0].push_back({b, p, 0});
        }
    }
    dijkstra();
    if(dis[en][0] == 1e9) cout << -1;
    else cout << dis[en][0];
    return 0;
}

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