Submission #1125455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125455		ALTAKEXE	Robots (APIO13_robots)	C++17	100 / 100	512 ms	142504 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define INF INT_MAX
#define FOR(i, b) for (int i = 0; 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;
const int MV = 502 * 502;
const int ME = 502 * 502 * 4 * 2;
struct point
{
        point() {}
        point(int x, int y) : x(x), y(y) {}
        int x, y;
        int value() { return 500 * (x - 1) + y; }
} inp[10];
int n, w, h;
int xx[4] = {-1, 0, 1, 0}, yy[4] = {0, 1, 0, -1};
char ch[510][510];
bool wall[510][510];
bool m_check[4][510][510];
bool A[510][510], C[510][510];
bool p[MV];
int Q[MV][2];
short b_check[MV];
int Dp[9][9][502][502];
typedef pair<int, int> P;
vector<point> has;
int st[MV], en[ME];
int nxt[ME];
int c;
vector<int> V[2500020];
inline int tr(int x, int y) { return 500 * (x - 1) + y; }
P itr(int x) { return P((x - 1) / 500 + 1, (x - 1) % 500 + 1); }
void add(int s, int d)
{
        c++;
        nxt[c] = st[s];
        st[s] = c;
        en[c] = d;
}
void make_edge()
{
        for (int i = 1; i <= h; i++)
        {
                for (int j = 1; j <= w; j++)
                {
                        for (int k = 0; k < 4; k++)
                        {
                                if (wall[i + xx[k ^ 2]][j + yy[k ^ 2]])
                                        continue;
                                int ink = k;
                                int tx = i, ty = j;
                                if (A[i][j])
                                        ink = (ink + 1) % 4;
                                else if (C[i][j])
                                        ink = (ink ? ink - 1 : 3);
                                while (!m_check[ink][tx][ty] && wall[tx][ty])
                                {
                                        add(tr(tx, ty), tr(i, j));
                                        m_check[ink][tx][ty] = 1;
                                        tx += xx[ink];
                                        ty += yy[ink];
                                        if (A[tx][ty])
                                                ink = (ink + 1) % 4;
                                        else if (C[tx][ty])
                                                ink = (ink ? ink - 1 : 3);
                                }
                        }
                }
        }
}
void BFS(int x)
{
        int fr = 1, re = 0;
        int vx = inp[x].value();
        Q[0][0] = vx, Q[0][1] = 0;
        b_check[vx] = x + 1;
        while (fr != re)
        {
                int i;
                int tx = Q[re][0];
                for (i = st[tx]; i; i = nxt[i])
                {
                        if (b_check[en[i]] == x + 1)
                                continue;
                        b_check[en[i]] = x + 1;
                        Q[fr][0] = en[i];
                        Q[fr][1] = Q[re][1] + 1;
                        fr++;
                }
                P tmp = itr(Q[re][0]);
                Dp[x][x][tmp.ff][tmp.ss] = Q[re++][1];
        }
}
void Merge(int a, int b, int c)
{
        memset(p, 0, sizeof(p));
        int mx = 0;
        int i, j;
        for (i = 1; i <= h; i++)
        {
                for (j = 1; j <= w; j++)
                {
                        if (Dp[a][b][i][j] == INF || Dp[b + 1][c][i][j] == INF)
                                continue;
                        int tmp2 = Dp[a][b][i][j] + Dp[b + 1][c][i][j];
                        V[tmp2].push_back(tr(i, j));
                        mx = max(mx, tmp2);
                }
        }
        for (i = 1; i <= mx; i++)
        {
                if (V[i].empty())
                        continue;
                for (j = 0; j < V[i].size(); j++)
                {
                        if (p[V[i][j]])
                                continue;
                        p[V[i][j]] = 1;
                        P tmp = itr(V[i][j]);
                        Dp[a][c][tmp.ff][tmp.ss] = min(Dp[a][c][tmp.ff][tmp.ss], i);
                        for (int k = st[V[i][j]]; k; k = nxt[k])
                        {
                                if (p[en[k]])
                                        continue;
                                V[i + 1].push_back(en[k]);
                                mx = max(mx, i + 1);
                        }
                }
                V[i].clear();
        }
}
void init(int x, int y)
{
        for (int i = 1; i <= h; i++)
        {
                for (int j = 1; j <= w; j++)
                        Dp[x][y][i][j] = INF;
        }
}

int main()
{
        cin >> n >> w >> h;
        for (int i = 1; i <= h; i++)
        {
                cin >> ch[i] + 1;
                for (int j = 1; j <= w; j++)
                {
                        if (ch[i][j] != 'x')
                                wall[i][j] = 1;
                        if (ch[i][j] <= '9' && ch[i][j] >= '1')
                                inp[ch[i][j] - '1'] = point(i, j);
                        if (ch[i][j] == 'A')
                                A[i][j] = 1;
                        else if (ch[i][j] == 'C')
                                C[i][j] = 1;
                }
        }
        make_edge();
        for (int i = 0; i < n; i++)
                BFS(i);
        for (int i = 0; i < n; i++)
        {
                for (int j = 1; j <= h; j++)
                {
                        for (int k = 1; k <= w; k++)
                        {
                                if (inp[i].x == j && inp[i].y == k)
                                        continue;
                                if (!Dp[i][i][j][k])
                                        Dp[i][i][j][k] = INF;
                        }
                }
        }
        for (int i = 1; i < n; i++)
        {
                for (int j = 0; j < n - i; j++)
                {
                        init(j, j + i);
                        for (int k = 0; k < i; k++)
                        {
                                Merge(j, j + k, j + i);
                        }
                }
        }
        int ans = INF;
        for (int i = 1; i <= h; i++)
                for (int j = 1; j <= w; j++)
                        ans = min(ans, Dp[0][n - 1][i][j]);
        cout << (ans == INF ? -1 : ans) << endl;
        return 0;
}

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