Submission #444684

#	Time	Username	Problem	Language	Result	Execution time	Memory
444684		Deepesson	Mecho (IOI09_mecho)	C++17	100 / 100	554 ms	4480 KiB

mecho

#include <bits/stdc++.h>
#define MAX 850
std::string mapa[MAX];
typedef std::pair<int,int> pii;
bool proibido[MAX][MAX]={},nobees[MAX][MAX]={};
int N,K;
typedef std::pair<int,pii> pip;
std::vector<pii> hon;
void avancar(void) {
    std::vector<pii> honfut;
    for(auto&x:hon) {
        #define PUSH(A,B) if(A>=0&&B>=0&&A<N&&B<N&&!proibido[A][B]&&!nobees[A][B]){proibido[A][B]=true;honfut.push_back({A,B});}
        PUSH(x.first+1,x.second);
        PUSH(x.first-1,x.second);
        PUSH(x.first,x.second+1);
        PUSH(x.first,x.second-1);
    }
    hon=honfut;
}
bool vis[MAX][MAX]={};
bool testar(int x,int s) {
    hon.clear();
    memset(&proibido[0][0],0,sizeof(proibido));
    memset(&nobees[0][0],0,sizeof(nobees));
    memset(&vis[0][0],0,sizeof(vis));
    pii inicio,fim;
    for(int i=0;i!=N;++i){
        for(int j=0;j!=N;++j){
            if(mapa[i][j]=='H'){
                proibido[i][j]=true;
                hon.push_back({i,j});
            }else if(mapa[i][j]=='M') {
                inicio={i,j};
            }else if(mapa[i][j]=='D') {
                nobees[i][j]=true;
                fim={i,j};
            }else if(mapa[i][j]=='T'){
                nobees[i][j]=true;
                proibido[i][j]=true;
            }
        }
    }
    for(int i=0;i!=x;++i)avancar();
    std::queue<pip> queue;
    queue.push({0,inicio});
    int laste=0;
    while(queue.size()) {
        auto _ = queue.front();
        queue.pop();
        int mov = _.first/s;
        if(mov>laste){
            laste=mov;
            avancar();
        }
        if(vis[_.second.first][_.second.second]||proibido[_.second.first][_.second.second])continue;
        vis[_.second.first][_.second.second]=true;
        if(_.second==fim)return true;
        #define QPUSH(A,B) if(A>=0&&B>=0&&A<N&&B<N)queue.push({_.first+1,{A,B}});
        QPUSH(_.second.first+1,_.second.second);
        QPUSH(_.second.first-1,_.second.second);
        QPUSH(_.second.first,_.second.second+1);
        QPUSH(_.second.first,_.second.second-1);
    }
    return false;
}
int main()
{
    std::cin>>N>>K;
    for(int i=0;i!=N;++i)std::cin>>mapa[i];
    if(!testar(0,K)) {
        std::cout<<-1<<"\n";
        return 0;
    }
    int l=0,r=N*N;
    while(l<r) {
        int m = (l+r)/2 + ((l+r)&1);
        if(testar(m,K)) {
            l=m;
        }else r=m-1;
    }
    std::cout<<l<<"\n";
}

• Subtask 1: 100 / 100