Submission #499610

#	Time	Username	Problem	Language	Result	Execution time	Memory
499610		Fake4Fun	Mecho (IOI09_mecho)	C++14	100 / 100	198 ms	6952 KiB

mecho

// source: https://oj.uz/problem/view/IOI09_mecho

#include<iostream>
#include<queue>
#define pa pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=802, oo=1e9;
constexpr int X[]={0,1,0,-1,0};
int n,s;
char c[N][N];
int Ong[N][N],Gau[N][N];
pa St,Fi;
queue<pa> q;
bool inside(int x,int y){
    return 1<=x&&x<=n&&1<=y&&y<=n;
}
void BFSOng(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(c[i][j]=='H') Ong[i][j]=0, q.push({i,j});
            else Ong[i][j]=oo;
        }
    while(!q.empty()){
        pa P=q.front(); q.pop();
        for(int k=0;k<4;k++){
            int nx=P.fi+X[k], ny=P.se+X[k+1];
            if(inside(nx,ny)&&c[nx][ny]!='D'&&c[nx][ny]!='T')
                if(Ong[nx][ny]==oo) Ong[nx][ny]=Ong[P.fi][P.se]+1, q.push({nx,ny});
        }
    }
}
bool check(int x){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(c[i][j]=='M') Gau[i][j]=0, q.push({i,j});
            else Gau[i][j]=oo;
        }
    for(int i=x,step=s;!q.empty();i++,step+=s) while(!q.empty()){
        pa P=q.front();
        if(Gau[P.fi][P.se]==step) break;
        if(P==Fi) return 1;
        q.pop();
        if(Ong[P.fi][P.se]<=i) continue;
        for(int k=0;k<4;k++){
            int nx=P.fi+X[k], ny=P.se+X[k+1];
            if(inside(nx,ny)&&c[nx][ny]!='T')
                if(Ong[nx][ny]>i&&Gau[nx][ny]==oo) Gau[nx][ny]=Gau[P.fi][P.se]+1, q.push({nx,ny});
        }
    }
    return 0;
}
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>c[i][j];
            if(c[i][j]=='M') St={i,j};
            if(c[i][j]=='D') Fi={i,j};
        }
    BFSOng();
    int l=0, r=Ong[St.fi][St.se], ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid, l=++mid;
        else r=--mid;
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 100 / 100