Submission #364646

#	Time	Username	Problem	Language	Result	Execution time	Memory
364646		parsabahrami	Robots (APIO13_robots)	C++17	100 / 100	1287 ms	117108 KiB

robots

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e2 + 10, MOD = 1e9 + 7;
int M[N][N], shit[4][N][N], dp[10][10][N][N], n, m, k; pii G[4][N][N]; // wtf is this
char A[N][N]; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

pii go(int x, int y, int d) {
    if (~G[d][x][y].F) return G[d][x][y];
    if (shit[d][x][y]) return G[d][x][y] = {-1, -1};
    int nxt = d;
    shit[d][x][y] = 1;
    if (A[x][y] == 'A') nxt = (nxt + 1) % 4;
    if (A[x][y] == 'C') nxt = (nxt - 1 + 4) % 4;
    int nx = dx[nxt] + x, ny = dy[nxt] + y;
    if (nx <= 0 || nx > n || ny > m || ny <= 0 || A[nx][ny] == 'x') return G[d][x][y] = {x, y};
    return G[d][x][y] = go(nx, ny, nxt);
}

int main() {
    for (int i = 0; i < 4; i++) 
        for (int j = 0; j < N; j++) 
            for (int l = 0; l < N; l++) G[i][j][l] = {-1, -1};
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", A[i] + 1);
    }
    for (int l = 0; l < 10; l++) 
        for (int r = 0; r < 10; r++) 
            for (int i = 0; i < N; i++) fill(dp[l][r][i], dp[l][r][i] + N, MOD);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i][j] != 'x') for (int d = 0; d < 4; d++) go(i, j, d);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i][j] != 'x' && A[i][j] != '.' && A[i][j] != 'A' && A[i][j] != 'C') dp[A[i][j] - '0'][A[i][j] - '0'][i][j] = 0;
        }
    }
    for (int sz = 1; sz <= k; sz++) {
        for (int l = 1; l + sz - 1 <= k; l++) {
            int r = l + sz - 1; deque<pii> q;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    for (int t = l; t < r; t++) dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][t][i][j] + dp[t + 1][r][i][j]);
                    if (dp[l][r][i][j] < MOD) q.push_back({i, j});
                }
            }
            sort(q.begin(), q.end(), [&] (pii x, pii y) { return dp[l][r][x.F][x.S] < dp[l][r][y.F][y.S]; });
            while (SZ(q)) {
                int x = q.front().F, y = q.front().S; q.pop_front();
                M[x][y] = 0;
                for (int d = 0; d < 4; d++) {
                    if (~G[d][x][y].F) {
                        int nx = G[d][x][y].F, ny = G[d][x][y].S;
                        if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) {
                            dp[l][r][nx][ny] = dp[l][r][x][y] + 1;
                            if (M[nx][ny]) continue;
                            M[nx][ny] = 1;
                            q.push_back({nx, ny});
                        }
                    }
                }
            }
        }
    }
    int ret = MOD;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) ret = min(ret, dp[1][k][i][j]);
    printf("%d\n", ret == MOD ? -1 : ret);
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d%d", &k, &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         scanf("%s", A[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40