Submission #86581

#	Time	Username	Problem	Language	Result	Execution time	Memory
86581		Alexa2001	Robots (APIO13_robots)	C++17	0 / 100	52 ms	50580 KiB

robots

#include <bits/stdc++.h>

using namespace std;


const int Nmax = 505;
const int inf = 0x3f3f3f3f;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

struct Pos
{
    int x, y, d;
    bool operator < (const Pos &other) const
    {
        return d > other.d;
    }
};
struct Pair
{
    int x, y;
};

Pair End[Nmax][Nmax][4];
int D[Nmax][Nmax][50];
int W, H, N;
char a[Nmax][Nmax];

int code(int x, int y)
{
    return y * (y-1) / 2 + (x-1);
}

void compute_states()
{
    int i, j;
    for(i=0; i<=W || i<=H; ++i)
        a[i][0] = a[0][i] = a[W+1][i] = a[H+1][i] = 'x';

    int x, y, k;
    queue<Pos> q;

    for(i=1; i<=W; ++i)
        for(j=1; j<=H; ++j)
            for(k=0; k<4; ++k)
            {
                x = i + dx[k];
                y = j + dy[k];

                if(a[x][y] == 'x')
                {
                    End[i][j][k] = {i, j};
                    q.push({i, j, k});
                }
            }

    while(q.size())
    {
        x = q.front().x;
        y = q.front().y;
        k = q.front().d;
        q.pop();
        Pair Now = End[x][y][k];

        if(a[x][y] == 'A') k = (k+3) % 4;
            else if(a[x][y] == 'C') k = (k+1) % 4;

        x -= dx[k];
        y -= dy[k];
        if(End[x][y][k].x == 0 && a[x][y] != 'x')
        {
            End[x][y][k] = Now;
            q.push({x, y, k});
        }
    }

    for(i=1; i<=W; ++i)
        for(j=1; j<=H; ++j)
            if(a[i][j] == 'A')
            {
                auto aux = End[i][j][0];
                for(k=0; k<3; ++k) End[i][j][k] = End[i][j][k+1];
                End[i][j][3] = aux;
            }
            else if(a[i][j] == 'C')
            {
                auto aux = End[i][j][3];
                for(k=3; k; --k) End[i][j][k] = End[i][j][k-1];
                End[i][j][0] = aux;
            }
}


void optimize(int K)
{
    priority_queue<Pos> heap;

    int i, j;
    for(i=1; i<=W; ++i)
        for(j=1; j<=H; ++j)
            if(D[i][j][K] != inf) heap.push({i, j, D[i][j][K]});

    int x, y, X, Y, k;
    while(heap.size())
    {
        x = heap.top().x;
        y = heap.top().y;
        if(D[x][y][K] != heap.top().d)
        {
            heap.pop();
            continue;
        }
        heap.pop();

        for(k=0; k<4; ++k)
        {
            X = End[x][y][k].x;
            Y = End[x][y][k].y;
            if(a[X][Y] == 'x' || D[X][Y][K] <= D[x][y][K]) continue;

            D[X][Y][K] = D[x][y][K] + 1;
            heap.push({X, Y, D[X][Y][K]});
        }
    }
}

void init_states()
{
    int i, j;

    memset(D, inf, sizeof(D));

    for(i=1; i<=W; ++i)
        for(j=1; j<=H; ++j)
            if(isdigit(a[i][j]))
            {
                a[i][j] -= '0';
                D[i][j][code(a[i][j], a[i][j])] = 0;
            }
    for(i=1; i<=N; ++i)
        optimize(code(i, i));
}

void solve(int A, int B)
{
    int i, j, k;

    for(i=1; i<=W; ++i)
        for(j=1; j<=H; ++j)
            for(k=A; k<B; ++k)
                D[i][j][code(A,B)] = min(D[i][j][code(A,B)], D[i][j][code(A, k)] + D[i][j][code(k+1, B)]);
    optimize(code(A, B));
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, j;
    cin >> N >> H >> W;
    for(i=1; i<=W; ++i) cin >> (a[i] + 1);

    compute_states();
    init_states();

    for(i=N; i; --i)
        for(j=i+1; j<=N; ++j)
            solve(i, j);

    int ans = inf;
    for(i=1; i<=W; ++i)
        for(j=1; j<=H; ++j)
            ans = min(ans, D[i][j][code(1, N)]);

    cout << (ans == inf ? -1 : ans) << '\n';

    return 0;
}

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