oj.uz

Submission #1019005

# Submission time Handle Problem Language Result Execution time Memory
1019005 2024-07-10T11:54:29 Z coolboy19521 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 468 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 0 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -