oj.uz

Submission #560511

# Submission time Handle Problem Language Result Execution time Memory
560511 2022-05-11T14:57:37 Z Cyanmond Robots (APIO13_robots) C++17
100 / 100
 1098 ms 89836 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]);
            }

            deque<tuple<int,int,int>> deq;
            REP(i, H) REP(j, W) if (dist[i][j][l][r] != inf) { deq.push_back({dist[i][j][l][r], i, j}); }
            sort(deq.begin(),deq.end());
            while (not deq.empty()) {
                const auto [nc, h, w] = deq.front();
                deq.pop_front();
                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)) {
                        deq.push_front({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 0 ms 340 KB Output is correct
5 Correct 1 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 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 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 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 181 ms 33872 KB Output is correct
12 Correct 23 ms 33472 KB Output is correct
13 Correct 66 ms 34176 KB Output is correct
14 Correct 360 ms 34232 KB Output is correct
15 Correct 156 ms 33700 KB Output is correct

Subtask #4
40.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 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 181 ms 33872 KB Output is correct
12 Correct 23 ms 33472 KB Output is correct
13 Correct 66 ms 34176 KB Output is correct
14 Correct 360 ms 34232 KB Output is correct
15 Correct 156 ms 33700 KB Output is correct
16 Correct 284 ms 88120 KB Output is correct
17 Correct 1098 ms 89836 KB Output is correct
18 Correct 344 ms 88820 KB Output is correct
19 Correct 306 ms 88124 KB Output is correct
20 Correct 784 ms 89268 KB Output is correct