제출 #39819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39819		nickyrio	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	1 ms	50760 KiB

skyscraper

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i)
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 30030
#define sqrtN 200
#define taskname ""

using namespace std;

int n, m, b[N], p[N];

struct data {
    int u, jump;
    long long d;
};

struct cmp{
    bool operator() (const data &a, const data &b) {
        return a.d > b.d;
    }
};

priority_queue<data, vector<data>, cmp> heap;
long long d[N][sqrtN];
vector<int> smallJump[N], largeJump[N];//, smallJumpVer[N];

void Dijkstra() {
    REP(i, n + 1) REP(j, (int)sqrt(n) + 1) d[i][j] = 1e18;
    d[0][0] = 0;
    heap.push(data({0, 0, 0}));
    while (!heap.empty()) {
        data u = heap.top();
        heap.pop();
        if (u.u == 1) {
            cout << u.d;
            return;
        }
        if (d[u.u][u.jump] != u.d) continue;
        if (u.jump == 0) {
            // Change value of jump
            for (int jump : smallJump[u.u]) {
                if (d[u.u][jump] > d[u.u][0]) {
                    d[u.u][jump] = d[u.u][0];
                    heap.push(data({u.u, jump, d[u.u][0]}));
                }
            }
            // Large jump ( <= sqrt(n) times because jump > sqrt(n) )
            for (int jump : largeJump[u.u]) {
                int newU = u.u - jump, c = 0;
                while (newU >= 0) {
                    ++c;
                    if (d[newU][0] > d[u.u][0] + c) {
                        d[newU][0] = d[u.u][0] + c;
                        heap.push(data({newU, 0, d[newU][0]}));
                    }
                    newU -= jump;
                }
                newU = u.u + jump, c = 0;
                while (newU <= n) {
                    ++c;
                    if (d[newU][0] > d[u.u][0] + c) {
                        d[newU][0] = d[u.u][0] + c;
                        heap.push(data({newU, 0, d[newU][0]}));
                    }
                    newU += jump;
                }
            }
        }
        else {
            // Jump left - right
            int newU = u.u - u.jump;
            if (newU >= 0 && d[newU][u.jump] > d[u.u][u.jump] + 1) {
                d[newU][u.jump] = d[u.u][u.jump] + 1;
                heap.push(data({newU, u.jump, d[newU][u.jump]}));
            }
            newU = u.u + u.jump;
            if (newU <= n && d[newU][u.jump] > d[u.u][u.jump] + 1) {
                d[newU][u.jump] = d[u.u][u.jump] + 1;
                heap.push(data({newU, u.jump, d[newU][u.jump]}));
            }
            // Change Jump to 0
            if (d[u.u][0] > d[u.u][u.jump]) {
                d[u.u][0] = d[u.u][u.jump];
                heap.push(data({u.u, 0, d[u.u][0]}));
            }
        }
    }
    cout << -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    FOR(i, 1, m) {
        int p, b;
        cin >> b >> p;
        if (p <= (int) sqrt(n)) smallJump[b].push_back(p);
        else largeJump[b].push_back(p);
    }
    Dijkstra();
}

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