제출 #311124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311124		lohacho	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1095 ms	109300 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];
vector<pair<int, int>> way[NS];
int far[NS], chk[NS];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
map<int, int> cnt[NS];
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];
        if(i == 1 && B[0] == B[1]){
            cout << 0;
            return 0;
        }
        if(cnt[B[i]][P[i]]){
            --i, --M;
            continue;
        }
        cnt[B[i]][P[i]] = i + 1;
        put[B[i]].push_back(i);
    }
    for(int i = 0; i < M; ++i){
        int now = B[i], mov = 0;
        while(now < N){
            if(now > B[i] && cnt[now][P[i]]){
                way[i].push_back({cnt[now][P[i]] - 1, mov});
                break;
            }
            for(auto&in:put[now]){
                way[i].push_back({in, mov});
            }
            now += P[i], ++mov;
        }
        now = B[i] - P[i], mov = 1;
        while(now >= 0){
            if(cnt[now][P[i]]){
                way[i].push_back({cnt[now][P[i]] - 1, mov});
                break;
            }
            for(auto&in:put[now]){
                way[i].push_back({in, mov});
            }
            now -= P[i], ++mov;
        }
    }
    pq.push({0, 0});
    for(int i = 0; i < M; ++i){
        far[i] = MOD;
    }
    far[0] = 0;
    while(!pq.empty()){
        while(!pq.empty() && chk[pq.top().second]){
            pq.pop();
        }
        if(pq.empty()){
            break;
        }
        auto top = pq.top(); pq.pop();
        chk[top.second] = 1;
        for(auto&nxt:way[top.second]){
            if(far[top.second] + nxt.second < far[nxt.first]){
                far[nxt.first] = far[top.second] + nxt.second;
                pq.push({far[nxt.first], nxt.first});
            }
        }
    }
    if(far[1] == MOD){
        cout << -1;
    }
    else{
        cout << far[1];
    }
    return 0;
}

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