Submission #1019005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019005		coolboy19521	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	468 KiB

skyscraper

#include "bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 3e4 + 12;

bool vi[sz][sz];
int b[sz], p[sz];
int a[sz];
int r, n;

void bfs(int x) {
    queue<vector<int>> q;
    q.push({0, x, b[x]});

    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        int d = t[0];
        int v = t[1];
        int bs = t[2];
        int u = a[bs];

     //   cout << d << ' ' << v << ' ' << u << '\n';

        if (2 == u) {
            r = d;
            return;
        }

        int tur = bs + p[u];
        int tul = bs - p[u];
        int tvr = bs + p[v];
        int tvl = bs - p[v];

        if (tur <= n && !vi[u][tur]) {
            q.push({d + 1, u, tur});
            vi[u][tur] = true;
        }
        if (0 < tul && !vi[u][tul]) {
            q.push({d + 1, u, tul});
            vi[u][tul] = true;
        }
        if (tvr <= n && !vi[v][tvr]) {
            q.push({d + 1, v, tvr});
            vi[v][tvr] = true;
        }
        if (0 < tvl && !vi[v][tvl]) {
            q.push({d + 1, v, tvl});
            vi[v][tvl] = true;
        }
    }
}


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int m;
    cin >> n >> m;

    for (int i = 1; i <= m; i ++) {
        cin >> b[i] >> p[i];
        b[i] ++;
        a[b[i]] = i;
    }

    bfs(1);

    cout << r << '\n';
}

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