oj.uz

Submission #391805

# Submission time Handle Problem Language Result Execution time Memory
391805 2021-04-20T00:24:44 Z ocarima Robots (APIO13_robots) C++14
100 / 100
 1325 ms 156824 KB 
#include<bits/stdc++.h>

using namespace std;

// PES 2021 - abril.  "Bacterias alienigenas" (60 pts: DFS + Busqueda priorizada sobre estado ampliado usando multiples colas en vez de cola priorizada)

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

#define MAX_N 503
#define MAX_BACTERIA 10
#define CICLADO 1000

#define norte 0
#define este 1
#define sur 2
#define oeste 3
#define invalido 0
#define valido 1
#define rotahorario 2
#define rotaantihorario 3

#define fila first
#define columna second

#define inicio first.first
#define fin first.second
#define cfila second.first
#define ccolumna second.second

#define horario(x) ((x + 1) & 3)
#define antihorario(x) ((x + 3) & 3)
#define une(a, b, c, d) ((a << 24) | (b << 20) | (c << 10) | d)
#define binicio(x) (x >> 24)
#define bfin(x) ((x >> 20) & 0xF)
#define cfila(x) ((x >> 10) & 0x3FF)
#define ccolumna(x) (x & 0x3FF)

int n, filas, columnas, mapa[MAX_N][MAX_N], res, tmp, maximo, cnt;
int dist[MAX_BACTERIA][MAX_BACTERIA][MAX_N][MAX_N];
pii destino[4][MAX_N][MAX_N], bact[MAX_BACTERIA], delta[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, coorddest;
int actual;
string s;

pii dfs(int fil, int col, int dir){
    if (destino[dir][fil][col].fila) return destino[dir][fil][col];  // SI YA CONOCE EL RESULTADO, DEVUELVELO
    if (mapa[fil][col] == invalido) return {fil, col}; // SI ES UNA POSICION INVALIDA DEVUELVELA

    int dirorig = dir;
    if (mapa[fil][col] == rotahorario) dir = horario(dir);
    else if (mapa[fil][col] == rotaantihorario) dir = antihorario(dir);

    if (mapa[fil + delta[dir].fila][col + delta[dir].columna] == invalido) return {fil, col};

    destino[dirorig][fil][col] = {CICLADO, CICLADO};
    return destino[dirorig][fil][col] = dfs(fil + delta[dir].fila, col + delta[dir].columna, dir);
}

int main()
{
    fastio;

    cin >> n >> columnas >> filas;

    // LEE EL MAPA
    rep(fil, 1, filas){
        cin >> s;
        rep(col, 1, columnas){
            if (s[col - 1] == '.') mapa[fil][col] = valido;
            else if (s[col - 1] == 'x') mapa[fil][col] = invalido;
            else if (s[col - 1] == 'A') mapa[fil][col] = rotaantihorario;
            else if (s[col - 1] == 'C') mapa[fil][col] = rotahorario;
            else{
                mapa[fil][col] = valido;
                bact[s[col - 1] - '0'].fila = fil;
                bact[s[col - 1] - '0'].columna = col;
            }
        }
    }

    // CALCULA A DONDE LLEGA UN ROBOT QUE SEA EMPUJADO EN CADA UNA DE LAS 4 DIRECCIONES DESDE CADA PUNTO POSIBLE DE ORIGEN.
    rep(fil, 1, filas){
        rep(col, 1, columnas){
            rep(dir, norte, oeste){
                destino[dir][fil][col] = dfs(fil, col, dir);
            }
        }
    }

    // HAZ UNA BUSQUEDA USANDO UNA COLA PRIORIZADA, EL ESTADO ES LA COORDENADA MAS LA ETIQUETA DE LA BACTERIA
    // LAS TRANSICIONES SON
    // LAS 4 DIRECCIONES EN QUE SE PUEDE EMPUJAR
    // LAS ETIQUETAS CON LAS QUE SE PUEDE UNIR
    // LOS ESTADOS VALIDOS SON AQUELLOS QUE REDUZCAN EL MEJOR CAMINO ENCONTRADO
    maximo = filas * columnas + 1;
    rep(fil, 1, filas) rep(col, 1, columnas) rep(b1, 1, n) rep(b2, b1, n) dist[b1][b2][fil][col] = maximo;

    vector<vector<int> > q(maximo);

    rep(b, 1, n){
        q[0].pb(une(b, b, bact[b].fila, bact[b].columna)); // INICIALMENTE AGREGA A LA COLA TODAS LAS BACTERIAS SOLAS CON SU POSICION
        dist[b][b][bact[b].fila][bact[b].columna] = 0;
    }

    cnt = 0;
    while (cnt < maximo){
        while (q[cnt].size()){
            actual = q[cnt].back();
            q[cnt].pop_back();

            // UNICAMENTE PROCESALO SI NADIE LO HA MEJORADO
            if (dist[binicio(actual)][bfin(actual)][cfila(actual)][ccolumna(actual)] == cnt){
                // HAZ TRANSICIONES DE EMPUJAR LA BACTERIA QUE SE TIENE EN LAS 4 DIRECCIONES
                rep(dir, norte, oeste){
                    coorddest = destino[dir][cfila(actual)][ccolumna(actual)];
                    if (dist[binicio(actual)][bfin(actual)][coorddest.fila][coorddest.columna] > cnt + 1){
                        q[cnt + 1].pb(une(binicio(actual), bfin(actual), coorddest.fila, coorddest.columna));
                        dist[binicio(actual)][bfin(actual)][coorddest.fila][coorddest.columna] = cnt + 1;
                    }
                }

                // TRANSICIONES QUE UNEN BACTERIAS
                rep(b, bfin(actual) + 1, n){ // VE SI PUEDES UNIR CON BACTERIAS CON ETIQUETAS "MAYORES"
                    tmp = dist[bfin(actual) + 1][b][cfila(actual)][ccolumna(actual)]; // FIJATE SI YA PUDO LLEGAR A ESA CASILLA CON LA ETIQUETA QUE BUSCAS
                    if (tmp < maximo && (tmp + cnt) < maximo && tmp + cnt < dist[binicio(actual)][b][cfila(actual)][ccolumna(actual)]){
                        q[tmp + cnt].pb(une(binicio(actual), b, cfila(actual), ccolumna(actual)));
                        dist[binicio(actual)][b][cfila(actual)][ccolumna(actual)] = tmp + cnt;
                    }
                }

                repa(b, binicio(actual) - 1, 1){ // VE SI PUEDES UNIRTE CON ETIQUETAS "MENORES"
                    tmp = dist[b][binicio(actual) - 1][cfila(actual)][ccolumna(actual)]; // FIJATE SI YA PUDO LLEGAR A ESA CASILLA CON LA ETIQUETA QUE BUSCAS
                    if (tmp < maximo && (tmp + cnt) < maximo && tmp + cnt < dist[b][bfin(actual)][cfila(actual)][ccolumna(actual)]){
                        q[tmp + cnt].pb(une(b, bfin(actual), cfila(actual), ccolumna(actual)));
                        dist[b][bfin(actual)][cfila(actual)][ccolumna(actual)] = tmp + cnt;
                    }
                }
            }
        }

        q[cnt].clear(); // ES NECESARIO LIMPIAR LA COLA PARA QUE NO SE QUEDE OCUPANDO MEMORIA.

        while (cnt < maximo && !q[cnt].size()) ++cnt;
    }

    res = maximo;
    rep(fil, 1, filas)
        rep(col, 1, columnas)
            res = min(res, dist[1][n][fil][col]);

    if (res == maximo) res = -1;
    cout << res;

    return 0;
}

Compilation message

robots.cpp:48: warning: "cfila" redefined
   48 | #define cfila(x) ((x >> 10) & 0x3FF)
      | 
robots.cpp:40: note: this is the location of the previous definition
   40 | #define cfila second.first
      | 
robots.cpp:49: warning: "ccolumna" redefined
   49 | #define ccolumna(x) (x & 0x3FF)
      | 
robots.cpp:41: note: this is the location of the previous definition
   41 | #define ccolumna second.second
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 181 ms 41584 KB Output is correct
12 Correct 11 ms 8780 KB Output is correct
13 Correct 21 ms 24560 KB Output is correct
14 Correct 408 ms 64496 KB Output is correct
15 Correct 67 ms 36556 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 181 ms 41584 KB Output is correct
12 Correct 11 ms 8780 KB Output is correct
13 Correct 21 ms 24560 KB Output is correct
14 Correct 408 ms 64496 KB Output is correct
15 Correct 67 ms 36556 KB Output is correct
16 Correct 54 ms 59804 KB Output is correct
17 Correct 1325 ms 156824 KB Output is correct
18 Correct 182 ms 65776 KB Output is correct
19 Correct 53 ms 59944 KB Output is correct
20 Correct 1081 ms 109568 KB Output is correct