Submission #404240

#	Time	Username	Problem	Language	Result	Execution time	Memory
404240		AlexRex0	Mecho (IOI09_mecho)	C++14	100 / 100	337 ms	6484 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

int n, s, xini, yini, xfin, yfin;
bool visitado[802][802];
char a[802][802];
int abejas[802][802];
struct dato{
    int x;
    int y;
    int tiempo;
};
int mov[4][2] = {{1,0}, {0,1}, {-1, 0}, {0, - 1}};
queue<dato> cola;
dato aux, nuevo;
void buscaA(){
    while(!cola.empty()){
        aux = cola.front();
        cola.pop();
        if(!visitado[aux.x][aux.y]){
            if(aux.x > n || aux.x < 1 || aux.y > n || aux.y < 1 || a[aux.x][aux.y] == 'T' || a[aux.x][aux.y] == 'D'){
            }else{
                visitado[aux.x][aux.y] = true;
                abejas[aux.x][aux.y] = aux.tiempo;
                for(int i = 0; i < 4; ++i){
                    nuevo.tiempo = aux.tiempo + 1;
                    nuevo.x = aux.x + mov[i][0];
                    nuevo.y = aux.y + mov[i][1];
                    cola.push(nuevo);
                }
            }
        }
    }
}

struct oso{
    int x;
    int y;
    int minutos;
    int cont;
};

oso inicial, frenteO, nuevoO;
queue<oso> colaO;
bool visitadoOso[802][802];

bool valido(int t){
    inicial.minutos = t;
    inicial.x = xini;
    inicial.y = yini;
    inicial.cont = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            visitadoOso[i][j] = false;
        }
    }
    colaO.push(inicial);
    while(!colaO.empty()){
        frenteO = colaO.front();
        colaO.pop();
        if(!visitadoOso[frenteO.x][frenteO.y]){
            if(frenteO.x > n || frenteO.x < 1 || frenteO.y > n || frenteO.y < 1 || a[frenteO.x][frenteO.y] == 'T' || a[frenteO.x][frenteO.y] == 'H'){
            }else{
                if(frenteO.minutos < abejas[frenteO.x][frenteO.y] || (frenteO.x == xfin && frenteO.y == yfin)){
                    visitadoOso[frenteO.x][frenteO.y] = true;
                    for(int i = 0; i < 4; ++i){
                        nuevoO.cont = frenteO.cont + 1;
                        nuevoO.minutos = frenteO.minutos;
                        nuevoO.x = frenteO.x + mov[i][0];
                        nuevoO.y = frenteO.y + mov[i][1];
                        if(nuevoO.cont >= s){
                            nuevoO.cont = 0;
                            nuevoO.minutos++;
                        }
                        colaO.push(nuevoO);
                    }
                }
            }
        }
    }
    if(visitadoOso[xfin][yfin]){
        return true;
    }
    return false;
}

int bs(){
    int inf = 0; int sup = n * n, medio, res = -1;
    while(inf <= sup){
        medio = (inf + sup) / 2;
        if(valido(medio)){
            res = medio;
            inf = medio + 1;
        }else{
            sup = medio - 1;
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> a[i][j];
            if(a[i][j] == 'H'){
                aux.x = i;
                aux.y = j;
                aux.tiempo = 0;
                cola.push(aux);
            }
            if(a[i][j] == 'M'){
                xini = i;
                yini = j;
            }
            if(a[i][j] == 'D'){
                xfin = i;
                yfin = j;
            }
        }
    }
    buscaA();
    cout << bs();
    return 0;
}

• Subtask 1: 100 / 100