oj.uz

Submission #86586

# Submission time Handle Problem Language Result Execution time Memory
86586 2018-11-26T18:45:35 Z Alexa2001 Robots (APIO13_robots) C++17
30 / 100
 1500 ms 55176 KB 
#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[i][H+1] = '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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 50296 KB Output is correct
2 Correct 43 ms 50420 KB Output is correct
3 Correct 43 ms 50496 KB Output is correct
4 Correct 43 ms 50520 KB Output is correct
5 Correct 45 ms 50596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 50296 KB Output is correct
2 Correct 43 ms 50420 KB Output is correct
3 Correct 43 ms 50496 KB Output is correct
4 Correct 43 ms 50520 KB Output is correct
5 Correct 45 ms 50596 KB Output is correct
6 Correct 55 ms 50596 KB Output is correct
7 Correct 43 ms 50596 KB Output is correct
8 Correct 44 ms 50596 KB Output is correct
9 Correct 43 ms 50596 KB Output is correct
10 Correct 43 ms 50596 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 50296 KB Output is correct
2 Correct 43 ms 50420 KB Output is correct
3 Correct 43 ms 50496 KB Output is correct
4 Correct 43 ms 50520 KB Output is correct
5 Correct 45 ms 50596 KB Output is correct
6 Correct 55 ms 50596 KB Output is correct
7 Correct 43 ms 50596 KB Output is correct
8 Correct 44 ms 50596 KB Output is correct
9 Correct 43 ms 50596 KB Output is correct
10 Correct 43 ms 50596 KB Output is correct
11 Execution timed out 1580 ms 55176 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 50296 KB Output is correct
2 Correct 43 ms 50420 KB Output is correct
3 Correct 43 ms 50496 KB Output is correct
4 Correct 43 ms 50520 KB Output is correct
5 Correct 45 ms 50596 KB Output is correct
6 Correct 55 ms 50596 KB Output is correct
7 Correct 43 ms 50596 KB Output is correct
8 Correct 44 ms 50596 KB Output is correct
9 Correct 43 ms 50596 KB Output is correct
10 Correct 43 ms 50596 KB Output is correct
11 Execution timed out 1580 ms 55176 KB Time limit exceeded
12 Halted 0 ms 0 KB -