Submission #1278568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278568		wedonttalkanymore	Robots (APIO13_robots)	C++20	0 / 100	0 ms	332 KiB

robots

// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
/*
    Wake up, I'm wake up
    Thu sang roi, em thay khong?
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<int, int>
#define fi first
#define se second

const int N = 5e2 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 19;

int n, w, h;
char a[N][N];
int dx[] = {-1, 0, 1, 0}; // tren, phai, duoi, trai
int dy[] = {0, 1, 0, -1};
pii pre[N][N][4];
int preid[N][N][4];

vector<array<array<int, 11>, 11>> dp;

vector<pii> stops;

pii dfs(int x, int y, int k) {
    if (pre[x][y][k].se == -1) {
        int nx = 0, ny = 0, nk = k;
        pre[x][y][k].se = 0;
        if (a[x][y] == 'A') {
            nk = (k + 3) % 4;
        }
        else if (a[x][y] == 'C') {
            nk = (k + 1) % 4;
        }
        nx = x + dx[nk];
        ny = y + dy[nk];
        if (nx < 1 || ny < 1 || nx > h || ny > w || a[nx][ny] == 'x') {
            pre[x][y][k] = make_pair(x, y);
        }
        else pre[x][y][k] = dfs(nx, ny, nk);
    }
    return pre[x][y][k];
}

void precompute() {
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int k = 0; k < 4; k++) {
                pre[i][j][k] = make_pair(-1, -1);
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int k = 0; k < 4; k++) {
                dfs(i, j, k);
            }
        }
    }
}

struct item {
    int id, L, R, val;
    bool operator <(const item &other) const {
        return val > other.val;
    }
};

int key(int x, int y) {
    return (x << 32) | y;
}

void dijkstra(int len) {
    int S = (int)stops.size();
    for (int s = 0; s < S; ++s) {
        for (int L = 1; L <= n; ++L)
            for (int R = 1; R <= n; ++R)
                dp[s][L][R] = inf;
    }

    priority_queue<item> q;
    if (len == 1) {
        for (int s = 0; s < S; ++s) {
            int i = stops[s].fi, j = stops[s].se;
            for (int R = 1; R <= n; R++) {
                if (a[i][j] >= '1' && a[i][j] <= '9' && (a[i][j]-'0') == R) {
                    dp[s][R][R] = 0;
                    q.push({s, R, R, 0});
                }
            }
        }
    }
    else {
        for (int s = 0; s < S; ++s) {
            int i = stops[s].fi, j = stops[s].se;
            for (int R = len; R <= n; R++) {
                int L = R - len + 1;
                int val = inf;
                for (int k = L; k < R; k++) {
                    val = min(val, dp[s][L][k] + dp[s][k + 1][R]);
                }
                if (val < inf) {
                    dp[s][L][R] = val;
                    q.push({s, L, R, val});
                }
            }
        }
    }

    while (!q.empty()) {
        auto it = q.top(); q.pop();
        int id = it.id, L = it.L, R = it.R, val = it.val;
        if (dp[id][L][R] != val) continue;
        int x = stops[id].fi, y = stops[id].se;
        for (int d = 0; d < 4; ++d) {
            int nid = preid[x][y][d];
            if (nid < 0) continue;
            if (dp[nid][L][R] > dp[id][L][R] + 1) {
                dp[nid][L][R] = dp[id][L][R] + 1;
                q.push({nid, L, R, dp[nid][L][R]});
            }
        }
    }
}

void solve() {
    for (int len = 1; len <= n; len++) {
        dijkstra(len);
    }
    int ans = inf;
    int S = (int)stops.size();
    for (int s = 0; s < S; ++s) {
        ans = min(ans, dp[s][1][n]);
    }
    cout << (ans >= inf ? -1 : ans);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> w >> h;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }
    precompute();
    {
        map<int, int> idx;
        for (int x = 1; x <= h; ++x) {
            for (int y = 1; y <= w; ++y) {
                for (int d = 0; d < 4; ++d) {
                    auto p = pre[x][y][d];
                    if (p.fi >= 1) {
                        int k = key(p.fi,p.se);
                        if (!idx.count(k)) {
                            idx[k] = stops.size();
                            stops.push_back(p);
                        }
                    }
                }
            }
        }
        for (int x = 1; x <= h; ++x) {
            for (int y = 1; y <= w; ++y) {
                if (a[x][y] >= '1' && a[x][y] <= '9') {
                    int k = key(x, y);
                    if (!idx.count(k)) {
                        idx[k] = stops.size();
                        stops.push_back({x,y});
                    }
                }
            }
        }
        for (int x = 1; x <= h; ++x) {
            for (int y = 1; y <= w; ++y) {
                for (int d = 0; d < 4; ++d) {
                    auto p = pre[x][y][d];
                    if (p.fi >= 1) preid[x][y][d] = idx[key(p.fi,p.se)];
                    else preid[x][y][d] = -1;
                }
            }
        }
    }

    int S = (int)stops.size();
    dp.assign(S, array<array<int,11>,11>());
    for (int s = 0; s < S; ++s)
        for (int L = 0; L <= 10; ++L)
            for (int R = 0; R <= 10; ++R)
                dp[s][L][R] = inf;

    solve();
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
robots.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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