제출 #847175

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847175		LaziChicken	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	3 ms	13400 KiB

skyscraper

//LaziChicken - 9/2023

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define dim 3
#define tii tuple <int, int, int>
#define inf 0x3f

const ll nx = 3e4+2;
const ll bx = 1e3+2;
const ll mod = 1e9+7;

//--------------------------------
int n, m, sq, st, ed, res = 1e9;
int dist[nx][103];
priority_queue <tii, vector<tii>, greater<tii>> pq;
vector <int> point[nx];

void dijkstra(){
    while(pq.size()){
        int val, u, x;
        tie(val, u, x) = pq.top();
        // cerr << val << " " << u << " " << x << "\n";
        pq.pop();
        if (dist[u][x] != val) continue;
        if (u == ed) res = min(res, val);
        for (auto p : point[u]){
            if (p < sq and u - p >= 0 and dist[u-p][p] > val + 1){
                pq.emplace(dist[u-p][p] = val + 1, u - p, p);
                // cerr << "PUT: " << val + 1 << " " << u - p << " " << p << "\n";
            }
            else if (p < sq and u + p < n and dist[u+p][p] > val + 1){
                pq.emplace(dist[u+p][p] = val + 1, u + p, p);
                // cerr << "PUT: " << val + 1 << " " << u + p << " " << p << "\n";
            }
            else if (p >= sq){
                for (int i = 1; u - i * p >= 0 or u + i * p < n; i++){
                    if (u - i * p >= 0 and dist[u-i*p][0] > val + i){
                        pq.emplace(dist[u-i*p][0] = val + i, u - i * p, 0);
                        // cerr << "PUT: " << val + i << " " << u - i * p << " " << 0 << "\n";
                    }
                    if (u + i * p < n and dist[u+i*p][0] > val + i){
                        pq.emplace(dist[u+i*p][0] = val + i, u + i * p, 0);
                        // cerr << "PUT: " << val + i << " " << u + i * p << " " << 0 << "\n";
                    }
                }
            }
        }
        if (x){
            if (u - x >= 0 and dist[u-x][x] > val + 1){
                pq.emplace(dist[u-x][x] = val + 1, u - x, x);
                // cerr << "PUT: " << val + 1 << " " << u - x << " " << x << "\n";
            }
            if (u + x < n and dist[u+x][x] > val + 1){
                pq.emplace(dist[u+x][x] = val + 1, u + x, x);
                // cerr << "PUT: " << val + 1 << " " << u + x << " " << x << "\n";
            }
        }
    }
}

//--------------------------------
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0, b, p; i < m; i++){
        cin >> b >> p;
        if (i == 0) st = b;
        if (i == 1) ed = b;
        point[b].emplace_back(p);
    }
    sq = 101;
    memset(dist, inf, sizeof(dist));
    for (auto p : point[st]){
        pq.emplace(0, st, p);
        dist[st][p] = 0;
    }
    dijkstra();
    if (res == 1e9) cout << -1;
    else cout << res;
}
/*
Note:

*/

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