oj.uz

Submission #915704

# Submission time Handle Problem Language Result Execution time Memory
915704 2024-01-24T15:09:02 Z Alcabel Robots (APIO13_robots) C++17
60 / 100
 145 ms 163840 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxc = 500, maxn = 10;
const int deltaX[4] = {0, -1, 0, 1}, deltaY[4] = {1, 0, -1, 0};
char t[maxc][maxc];
pair<int, int> dest[maxc][maxc][4];
char vis[maxc][maxc][4];
int w, h;

pair<int, int> getDest(int x, int y, int dir) {
    if (vis[x][y][dir] == 1) {
        dest[x][y][dir] = {-1, -1};
        return {-1, -1};
    }
    if (vis[x][y][dir] == 2) {
        return dest[x][y][dir];
    }
    vis[x][y][dir] = 1;
    int newDir = dir;
    if (t[x][y] == 'A') {
        newDir = (dir < 3 ? dir + 1 : 0);
    } else if (t[x][y] == 'C') {
        newDir = (dir > 0 ? dir - 1 : 3);
    }
    int newX = x + deltaX[newDir], newY = y + deltaY[newDir];
    if (newX < 0 || newX >= h || newY < 0 || newY >= w || t[newX][newY] == 'x') {
        dest[x][y][dir] = {x, y};
    } else {
        dest[x][y][dir] = getDest(newX, newY, newDir);
    }
    vis[x][y][dir] = 2;
    return dest[x][y][dir];
}

const int inf = 1e9;
int dist[maxc][maxc];
int dp[maxn][maxn][maxc][maxc];

void bfs(int sx, int sy) {
    static queue<pair<int, int>> q;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            dist[i][j] = -1;
        }
    }
    dist[sx][sy] = 0;
    q.emplace(sx, sy);
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int dir = 0; dir < 4; ++dir) {
            auto [newX, newY] = dest[x][y][dir];
            if (newX != -1 && dist[newX][newY] == -1) {
                dist[newX][newY] = dist[x][y] + 1;
                q.emplace(newX, newY);
            }
        }
    }
    int num = t[sx][sy] - '1';
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (dist[i][j] != -1) {
                dp[num][num][i][j] = dist[i][j];
            }
        }
    }
}

const int maxd = maxn * maxc * maxc + 10;
vector<pair<int ,int>> byDist[maxd];
int distT[maxd], tt;

void solve() {
    int n;
    cin >> n >> w >> h;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> t[i][j];
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            // cerr << "i: " << i << ", j: " << j << '\n';
            for (int dir = 0; dir < 4; ++dir) {
                if (t[i][j] == 'x') {
                    dest[i][j][dir] = {-1, -1};
                    vis[i][j][dir] = 2;
                } else {
                    dest[i][j][dir] = getDest(i, j, dir);
                }
                // cerr << "dir: " << dir << ", dest: " << dest[i][j][dir].first << ' ' << dest[i][j][dir].second << '\n';
            }
        }
    }
    for (int l = 0; l < n; ++l) {
        for (int r = 0; r < n; ++r) {
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    dp[l][r][i][j] = inf;
                }
            }
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (t[i][j] >= '1' && t[i][j] <= '9') {
                bfs(i, j);
            }
        }
    }
    tt = 0;
    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            // cerr << "l: " << l << ", r: " << r << '\n';
            int needcnt = 0, start = inf;
            ++tt;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    for (int m = l; m < r; ++m) {
                        dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m + 1][r][i][j]);
                    }
                    dist[i][j] = dp[l][r][i][j];
                    if (dist[i][j] != inf) {
                        ++needcnt;
                        if (distT[dist[i][j]] < tt) {
                            distT[dist[i][j]] = tt;
                            byDist[dist[i][j]].clear();
                        }
                        byDist[dist[i][j]].emplace_back(i, j);
                        start = min(start, dist[i][j]);
                    }
                    // cerr << "i: " << i << ", j: " << j << ", dist: " << dist[i][j] << '\n';
                }
            }
            while (needcnt > 0) {
                while (start < maxd && distT[start] < tt) {
                    ++start;
                }
                assert(start < maxd);
                while (!byDist[start].empty()) {
                    auto [i, j] = byDist[start].back();
                    byDist[start].pop_back();
                    dp[l][r][i][j] = dist[i][j];
                    --needcnt;
                    for (int dir = 0; dir < 4; ++dir) {
                        auto [newI, newJ] = dest[i][j][dir];
                        if (newI != -1 && dist[newI][newJ] > dist[i][j] + 1) {
                            ++needcnt;
                            int newd = dist[i][j] + 1;
                            dist[newI][newJ] = newd;
                            if (distT[newd] < tt) {
                                distT[newd] = tt;
                                byDist[newd].clear();
                            }
                            byDist[newd].emplace_back(newI, newJ);
                        }
                    }
                }
                ++start;
            }
        }
    }
    int ans = inf;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ans = min(ans, dp[0][n - 1][i][j]);
        }
    }
    if (ans == inf) {
        ans = -1;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 67932 KB Output is correct
2 Correct 19 ms 68156 KB Output is correct
3 Correct 19 ms 67928 KB Output is correct
4 Correct 19 ms 68192 KB Output is correct
5 Correct 19 ms 68184 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 67932 KB Output is correct
2 Correct 19 ms 68156 KB Output is correct
3 Correct 19 ms 67928 KB Output is correct
4 Correct 19 ms 68192 KB Output is correct
5 Correct 19 ms 68184 KB Output is correct
6 Correct 20 ms 68184 KB Output is correct
7 Correct 20 ms 67932 KB Output is correct
8 Correct 20 ms 67932 KB Output is correct
9 Correct 19 ms 68188 KB Output is correct
10 Correct 20 ms 68124 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 67932 KB Output is correct
2 Correct 19 ms 68156 KB Output is correct
3 Correct 19 ms 67928 KB Output is correct
4 Correct 19 ms 68192 KB Output is correct
5 Correct 19 ms 68184 KB Output is correct
6 Correct 20 ms 68184 KB Output is correct
7 Correct 20 ms 67932 KB Output is correct
8 Correct 20 ms 67932 KB Output is correct
9 Correct 19 ms 68188 KB Output is correct
10 Correct 20 ms 68124 KB Output is correct
11 Correct 81 ms 125520 KB Output is correct
12 Correct 24 ms 72284 KB Output is correct
13 Correct 45 ms 102996 KB Output is correct
14 Correct 139 ms 131664 KB Output is correct
15 Correct 73 ms 122960 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 67932 KB Output is correct
2 Correct 19 ms 68156 KB Output is correct
3 Correct 19 ms 67928 KB Output is correct
4 Correct 19 ms 68192 KB Output is correct
5 Correct 19 ms 68184 KB Output is correct
6 Correct 20 ms 68184 KB Output is correct
7 Correct 20 ms 67932 KB Output is correct
8 Correct 20 ms 67932 KB Output is correct
9 Correct 19 ms 68188 KB Output is correct
10 Correct 20 ms 68124 KB Output is correct
11 Correct 81 ms 125520 KB Output is correct
12 Correct 24 ms 72284 KB Output is correct
13 Correct 45 ms 102996 KB Output is correct
14 Correct 139 ms 131664 KB Output is correct
15 Correct 73 ms 122960 KB Output is correct
16 Correct 117 ms 150864 KB Output is correct
17 Runtime error 145 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -