oj.uz

Submission #560504

# Submission time Handle Problem Language Result Execution time Memory
560504 2022-05-11T14:45:49 Z Cyanmond Robots (APIO13_robots) C++17
60 / 100
 964 ms 163840 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)

constexpr int inf = 1050000000;

constexpr array<pair<int, int>, 4> dxy = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};

template <class T> bool chmin(T &a, const T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    int N, W, H;
    cin >> N >> W >> H;
    vector<string> S(H);
    for (auto &e : S) cin >> e;
    vector<vector<array<pair<int, int>, 4>>> dest(H, vector<array<pair<int, int>, 4>>(W));
    REP(i, H) REP(j, W) REP(k, 4) dest[i][j][k] = {-2, -2};

    auto calc_dest = [&](auto &&self, const int h, const int w, const int k) -> pair<int, int> {
        if (dest[h][w][k] == make_pair(-3, -3)) return dest[h][w][k] = {-1, -1};
        if (dest[h][w][k] != make_pair(-2, -2)) return dest[h][w][k];
        const int nh = h + dxy[k].first, nw = w + dxy[k].second;
        if (nh < 0 or nw < 0 or nh >= H or nw >= W) return dest[h][w][k] = {h, w};
        if (S[nh][nw] == 'x') return dest[h][w][k] = {h, w};
        if (S[nh][nw] == 'A') {
            dest[h][w][k] = {-3, -3};
            return dest[h][w][k] = self(self, nh, nw, (k + 3) % 4);
        }
        if (S[nh][nw] == 'C') {
            dest[h][w][k] = {-3, -3};
            return dest[h][w][k] = self(self, nh, nw, (k + 1) % 4);
        }
        return dest[h][w][k] = self(self, nh, nw, k);
    };

    REP(i, H) REP(j, W) REP(k, 4) calc_dest(calc_dest, i, j, k);

    vector dist(H, vector(W, vector(N, vector(N, inf))));
    REP(i, H) REP(j, W) if (S[i][j] >= '1' and S[i][j] < '1' + N) {
        const int v = S[i][j] - '1';
        chmin(dist[i][j][v][v], 0);
        REP(k, 4) {
            if (dest[i][j][k] != make_pair(-1, -1))
                chmin(dist[dest[i][j][k].first][dest[i][j][k].second][v][v], 1);
        }
    }

    REP(length, N) {
        REP(l, N - length) {
            const int r = l + length;
            REP(i, H) REP(j, W) {
                REP3(d, l, r) chmin(dist[i][j][l][r], dist[i][j][l][d] + dist[i][j][d + 1][r]);
            }

            priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                           greater<tuple<int, int, int>>>
                pq;
            REP(i, H) REP(j, W) if (dist[i][j][l][r] != inf) { pq.push({dist[i][j][l][r], i, j}); }
            while (not pq.empty()) {
                const auto [nc, h, w] = pq.top();
                pq.pop();
                if (nc > dist[h][w][l][r]) continue;
                REP(k, 4) {
                    const int nh = dest[h][w][k].first, nw = dest[h][w][k].second;
                    if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
                    if (chmin(dist[nh][nw][l][r], nc + 1)) {
                        pq.push({nc + 1, nh, nw});
                    }
                }
            }
        }
    }

    int ans = inf;
    REP(i, H) REP(j, W) chmin(ans, dist[i][j][0][N - 1]);
    if (ans == inf) ans = -1;
    cout << ans << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 296 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 392 ms 62740 KB Output is correct
12 Correct 20 ms 10836 KB Output is correct
13 Correct 155 ms 50616 KB Output is correct
14 Correct 964 ms 63380 KB Output is correct
15 Correct 297 ms 62456 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 392 ms 62740 KB Output is correct
12 Correct 20 ms 10836 KB Output is correct
13 Correct 155 ms 50616 KB Output is correct
14 Correct 964 ms 63380 KB Output is correct
15 Correct 297 ms 62456 KB Output is correct
16 Runtime error 139 ms 163840 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -