Submission #847196

#	Time	Username	Problem	Language	Result	Execution time	Memory
847196		LaziChicken	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1068 ms	17156 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 dist[u][p] > val){
                pq.emplace(dist[u][p] = val, u, p);
            }
            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));
  	dist[st][0] = 0;
  	pq.emplace(0, st, 0);
    dijkstra();
    if (res == 1e9) cout << -1;
    else cout << res;
}
/*
Note:
 
*/

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