oj.uz

Submission #560507

# Submission time Handle Problem Language Result Execution time Memory
560507 2022-05-11T14:54:00 Z Cyanmond Robots (APIO13_robots) C++17
60 / 100
 1500 ms 91308 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;
}

array<pair<int, int>, 4> dest[500][500];
int dist[500][500][9][9];

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) REP(l, N) REP(r, N) dist[i][j][l][r] = 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 214 ms 34216 KB Output is correct
12 Correct 25 ms 33464 KB Output is correct
13 Correct 87 ms 34188 KB Output is correct
14 Correct 784 ms 34836 KB Output is correct
15 Correct 203 ms 33924 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 214 ms 34216 KB Output is correct
12 Correct 25 ms 33464 KB Output is correct
13 Correct 87 ms 34188 KB Output is correct
14 Correct 784 ms 34836 KB Output is correct
15 Correct 203 ms 33924 KB Output is correct
16 Correct 274 ms 88188 KB Output is correct
17 Execution timed out 1594 ms 91308 KB Time limit exceeded
18 Halted 0 ms 0 KB -