Submission #1136226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136226		ALTAKEXE	Robots (APIO13_robots)	C++17	0 / 100	3 ms	6208 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define INF INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
int n, w, h;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
pair<int, int> m[500][500][4];
char s[501][501];
vector<pair<int, int>> g[500][500];
int cost[10][10][500][500];
pair<int, int> dfs(int x, int y, int d)
{
    if (x < 0)
        return {x + 1, y};
    if (y < 0)
        return {x, y + 1};
    if (x >= h)
        return {x - 1, y};
    if (y >= w)
        return {x, y - 1};
    if (s[x][y] == 'x')
        return {x + dx[d * d], y + dy[d * d]};
    if (m[x][y][d] != pair<int, int>{-1, -1})
        return m[x][y][d];
    int d2 = d;
    if (s[x][y] == 'A')
        d2 += 3, d2 &= 3;
    else if (s[x][y] == 'C')
        d2 += 1, d2 &= 3;
    m[x][y][d] = {-2, -2};
    return m[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2);
}
void bfs(int u, int v)
{
    auto c = cost[u][v];
    for (int k = u + 1; k < v; k++)
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                c[i][j] = min(c[i][j], cost[u][k][i][j] + cost[k][v][i][j]);
    queue<tuple<int, int, int>> q;
    vector<tuple<int, int, int>> q2;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (c[i][j] != INF)
                q2.push_back({c[i][j], i, j});
    sort(q2.begin(), q2.end(), greater<tuple<int, int, int>>());
    while (q.size() || q2.size())
    {
        bool ok = 0;
        if (!q2.size())
            ok = 1;
        else if (q.size() && get<0>(q.front()) < get<0>(q2.back()))
            ok = 1;
        auto [cost, x, y] = ok ? q.front() : q2.back();
        if (ok)
            q.pop();
        else
            q2.pop_back();
        for (auto [x2, y2] : g[x][y])
            if (min(c[x2][y2], cost + 1))
                q.push({c[x2][y2], x2, y2});
    }
}
int main()
{
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++)
        cin >> s[i];
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            for (int d = 0; d < 4; d++)
                dfs(i, j, d);
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            for (int d = 0; d < 4; d++)
                if (m[i][j][d] != pair<int, int>{-2, -2} && m[i][j][d] != pair<int, int>{i, j})
                    g[i][j].push_back(m[i][j][d]);
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (isdigit(s[i][j]))
                cost[s[i][j] - '1'][s[i][j] - '0'][i][j] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n - i; j++)
            bfs(j, j + i);
    int ans = INF;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            ans = min(ans, cost[0][n][i][j]);
    cout << ((ans == INF) ? -1 : ans) << endl;
    return 0;
}

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