Submission #1059009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059009		sammyuri	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	2 ms	4700 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 = 0; // 100
const int MAXN = 30000;
const int INF = 1e9;
int mintime[MAXN][SMALL + 1];
int dist[MAXN];
vector<int> doges[MAXN];
bitset<MAXN> todo[MAXN + 1];

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;
    }
    todo[0][startnode] = 1;
    dist[0] = 0;
    bool done = false;
    for (int t = 0; t <= n; t ++) {
        while (true) {
            int xx = todo[t]._Find_first();
            if (xx == MAXN) break;
            todo[t][xx] = false;
            int curnode = xx;
            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) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                    extratime = 0;
                    for (int j = curnode + doge; j < n; j += doge) {
                        extratime ++;
                        if (dist[j] > extratime + t) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                }
                // 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) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                    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) {
                            if (dist[j] != INF)
                                todo[dist[j]][j] = 0;
                            dist[j] = extratime + t;
                            todo[dist[j]][j] = 1;
                        }
                    }
                }
            }
            if (curnode == target) {
                done = true; break;
            }
        }
        if (done) break;
    }
    if (dist[target] == INF) {
        cout << -1 << endl;
    } else cout << dist[target] << endl;
    return 0;
}

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