제출 #1322079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1322079		aaaaaaaa	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	405 ms	35648 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e4 + 5;

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2>& pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ (hash2 << 1);
    }
};

vector<int> pos[mxN];
int n, m, x, y;
unordered_map<int, int> dp[mxN];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m;
    vector<int> d(m), s(m);
    for(int i = 0; i < m; ++i){
        cin >> d[i] >> s[i];
        if(i == 0) x = d[i], y = s[i];
        pos[d[i]].push_back(s[i]);
    }
    priority_queue<tuple<int, int, int>> pq;
    pq.push({0, x, y});
    dp[x][y] = 0;
    int ans = 2 * mxN;
    while(pq.size()){
        auto [dist, id, mov] = pq.top();
        pq.pop();
        dist = -dist;
        if(id == d[1]){
            ans = min(ans, dist);
            continue;
        }
        if(dp[id][mov] < dist) continue;
        for(auto it : pos[id]){
            if((id + it) <= (n - 1) && (!dp[id + it].count(it) || dp[id + it][it] > (dist + 1))){
                dp[id + it][it] = dist + 1;
                pq.push({-dp[id + it][it], id + it, it});
            }
            if((id - it) >= 0 && (!dp[id - it].count(it) || dp[id - it][it] > (dist + 1))){
                dp[id - it][it] = dist + 1;
                pq.push({-dp[id - it][it], id - it, it});
            }
        }
        if((id + mov) <= (n - 1) && (!dp[id + mov].count(mov) || dp[id + mov][mov] > (dist + 1))){
            dp[id + mov][mov] = dist + 1;
            pq.push({-dp[id + mov][mov], id + mov, mov});
        }
        if((id - mov) >= 0 && (!dp[id - mov].count(mov) || dp[id - mov][mov] > (dist + 1))){
            dp[id - mov][mov] = dist + 1;
            pq.push({-dp[id - mov][mov], id - mov, mov});
        }
    }
    if(ans == 2 * mxN) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}

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