oj.uz

Submission #1019017

# Submission time Handle Problem Language Result Execution time Memory
1019017 2024-07-10T12:02:50 Z coolboy19521 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 460 KB 
#include "bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 30012;

//vector<bool> vi[sz];
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 << ' ' << bs << '\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 && (tur >= 1) && !vi[u][tur]) {
            q.push({d + 1, u, tur});
            vi[u][tur] = true;
        }
        if (tul >= 1 && !vi[u][tul]) {
            q.push({d + 1, u, tul});
            vi[u][tul] = true;
        }
        if (tvr <= n && (tvr >= 1) && !vi[v][tvr]) {
            q.push({d + 1, v, tvr});
            vi[v][tvr] = true;
        }
        if (tvl >= 1 && !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 0 ms 460 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 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 #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 0 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 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -