Submission #281638

#	Time	Username	Problem	Language	Result	Execution time	Memory
281638		two_sides	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1108 ms	150260 KiB

skyscraper

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

struct info{
    int x, p, d, t;

    info(){}

    info(int x, int p, int d, int t):
    x(x), p(p), d(d), t(t){}

    bool operator < (const info &o)
    const {return d > o.d;}
};

const int N = 5e4 + 5;
const int K = 750;
priority_queue <info> pq;
int dis[N][K], di[N];
vector <int> has[N];
int b[N], p[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int m, n; cin >> m >> n;
    for (int i = 0; i < n; i++){
        cin >> b[i] >> p[i];
        has[b[i]].push_back(i);
    }
    memset(dis, 0x3f, sizeof dis);
    memset(di, 0x3f, sizeof di);
    if (p[0] <= K){
        dis[b[0]][p[0]] = 0;
        pq.emplace(b[0], p[0], 0, 0);
    }
    else {
        di[b[0]] = 0;
        for (int i : has[b[0]])
            pq.emplace(b[i], p[i], 0, 0);
    }
    while (!pq.empty()){
        auto u = pq.top(); pq.pop();
        if (u.p <= K){
            if (dis[u.x][u.p] < u.d) continue;
        }
        else {
            if (di[u.x] < u.d) continue;
        }
        if (u.x == b[1]){
            cout << u.d << '\n'; return 0;
        }
        if (!u.t){
            if (di[u.x] > u.d){
                pq.emplace(u.x, u.p, u.d, 1);
                di[u.x] = u.d;
            }
            if (u.p <= K){
                if (u.x + u.p <= m &&
                dis[u.x + u.p][u.p] > u.d + 1){
                    dis[u.x + u.p][u.p] = u.d + 1;
                    pq.emplace(u.x + u.p, u.p, u.d + 1, 0);
                }
                if (u.x - u.p >= 0 &&
                dis[u.x - u.p][u.p] > u.d + 1){
                    dis[u.x - u.p][u.p] = u.d + 1;
                    pq.emplace(u.x - u.p, u.p, u.d + 1, 0);
                }
            }
            else {
                for (int i = 1; u.x + i * u.p <= m; i++){
                    int nx = u.x + i * u.p;
                    if (di[nx] > u.d + i){
                        di[nx] = u.d + i;
                        pq.emplace(nx, u.p, u.d + i, 1);
                    }
                }
                for (int i = 1; u.x - i * u.p >= 0; i++){
                    int nx = u.x - i * u.p;
                    if (di[nx] > u.d + i){
                        di[nx] = u.d + i;
                        pq.emplace(nx, u.p, u.d + i, 1);
                    }
                }
            }
        }
        else {
            for (int i : has[u.x])
                pq.emplace(b[i], p[i], u.d, 0);
        }
    }
    cout << "-1\n"; return 0;
}

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