Submission #311131

#	Time	Username	Problem	Language	Result	Execution time	Memory
311131		lohacho	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	122 ms	6000 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)3e4 + 4;
int N, M;
int B[NS], P[NS];
int far[NS], chk[NS];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> put[NS];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i = 0; i < M; ++i){
        cin >> B[i] >> P[i];
        put[B[i]].push_back(P[i]);
    }
    for(int i = 0; i < N; ++i){
        sort(put[i].begin(), put[i].end());
        put[i].erase(unique(put[i].begin(), put[i].end()), put[i].end());
        far[i] = MOD;
    }
    far[B[0]] = 0;
    pq.push({0, B[0]});
    while(!pq.empty()){
        while(!pq.empty() && chk[pq.top().second]){
            pq.pop();
        }
        if(pq.empty()){
            break;
        }
        int now = pq.top().second; pq.pop();
        chk[now] = 1;
        for(auto&jump:put[now]){
            for(int mov = 1; now + mov * jump < N; ++mov){
                int nxt = now + mov * jump;
                if(far[now] + mov < far[nxt]){
                    far[nxt] = far[now] + mov;
                    pq.push({far[nxt], nxt});
                }
                int pos = lower_bound(put[nxt].begin(), put[nxt].end(), jump) - put[nxt].begin();
                if(pos < (int)put[nxt].size() && put[nxt][pos] == jump){
                    break;
                }
            }
        }
        for(auto&jump:put[now]){
            for(int mov = 1; now - mov * jump >= 0; ++mov){
                int nxt = now - mov * jump;
                if(far[now] + mov < far[nxt]){
                    far[nxt] = far[now] + mov;
                    pq.push({far[nxt], nxt});
                }
                int pos = lower_bound(put[nxt].begin(), put[nxt].end(), jump) - put[nxt].begin();
                if(pos < (int)put[nxt].size() && put[nxt][pos] == jump){
                    break;
                }
            }
        }
    }
    if(far[B[1]] == MOD){
        cout << -1;
    }
    else{
        cout << far[B[1]];
    }
    return 0;
}

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