제출 #1059018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059018		sammyuri	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	31 ms	15572 KiB

skyscraper

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

/*
we run dijkstra
let B = 100
for all doges that have p >= b, just simulate the jumps
how do we deal with the "small" doges??
note that the answer is never more than 30000...
*/

const int SMALL = 100;
const int MAXN = 30000;
const int INF = 1e9;
int mintime[MAXN][SMALL + 1];
int dist[MAXN];
vector<int> doges[MAXN];
priority_queue<pair<int, int>> pq;

int main() {
    int n; cin >> n;
    int m; cin >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 1; j <= SMALL; j ++)
            mintime[i][j] = INF;
    for (int i = 0; i < n; i ++)
        dist[i] = INF;
    int startnode = -1, target = -1;
    for (int i = 0; i < m; i ++) {
        int b, p; cin >> b >> p;
        if (i == 0)
            startnode = b;
        else if (i == 1)
            target = b;
        doges[b].push_back(p);
    }
    if (startnode == target) {
        cout << 0 << endl; return 0;
    }
    pq.push({0, startnode});
    dist[startnode] = 0;
    while (pq.size()) {
        pair<int, int> xx = pq.top(); pq.pop();
        int t = -xx.first;
        int curnode = xx.second;
        if (dist[curnode] != t)
            continue;
        for (auto doge : doges[curnode]) {
            // big doge
            if (doge > SMALL) {
                int extratime = 0;
                for (int j = curnode - doge; j >= 0; j -= doge) {
                    extratime ++;
                    if (dist[j] > extratime + t) {
                        dist[j] = extratime + t;
                        pq.push({-dist[j], j});
                    }
                }
                extratime = 0;
                for (int j = curnode + doge; j < n; j += doge) {
                    extratime ++;
                    if (dist[j] > extratime + t) {
                        dist[j] = extratime + t;
                        pq.push({-dist[j], j});
                    }
                }
            }
            // small doge
            else {
                // ignore entirely
                if (mintime[curnode][doge] <= t)
                    continue;
                mintime[curnode][doge] = t;
                int extratime = 0;
                for (int j = curnode - doge; j >= 0; j -= doge) {
                    extratime ++;
                    // stop
                    if (mintime[j][doge] <= t + extratime)
                        break;
                    mintime[j][doge] = t + extratime;
                    if (dist[j] > extratime + t) {
                        dist[j] = extratime + t;
                        pq.push({-dist[j], j});
                    }
                }
                extratime = 0;
                for (int j = curnode + doge; j < n; j += doge) {
                    extratime ++;
                    // stop
                    if (mintime[j][doge] <= t + extratime)
                        break;
                    mintime[j][doge] = t + extratime;
                    if (dist[j] > extratime + t) {
                        dist[j] = extratime + t;
                        pq.push({-dist[j], j});
                    }
                }
            }
        }
        if (curnode == target) {
            break;
        }
    }
    if (dist[target] == INF) {
        cout << -1 << endl;
    } else cout << dist[target] << endl;
    return 0;
}

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