Submission #53610

#	Time	Username	Problem	Language	Result	Execution time	Memory
53610		Diuven	Mecho (IOI09_mecho)	C++11	100 / 100	249 ms	6564 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=810, inf=2e9;

int n, s;
char B[MX][MX];
int xs, ys, xl, yl;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Y[MX][MX];

bool valid(int x, int y){
    return 1<=x && x<=n && 1<=y && y<=n && (B[x][y]=='G' || B[x][y]=='H');
}

void bees(){
    queue<pii> Q;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
            if(B[i][j]=='H') Y[i][j]=0, Q.push({i,j});
            else Y[i][j]=-1;
        }
    while(!Q.empty()){
        pii p=Q.front(); Q.pop();
        int x,y; tie(x,y)=p;
        for(int k=0; k<4; k++){
            int u=x+dx[k], v=y+dy[k];
            if(!valid(u,v) || Y[u][v]>=0) continue;
            Y[u][v]=Y[x][y]+s;
            Q.push({u,v});
        }
    }
}

int D[MX][MX];

bool solve(int t){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            D[i][j]=-1;
    queue<pii> Q;
    D[xs][ys]=t*s;
    if(D[xs][ys]>=Y[xs][ys]) return false;
    Q.push({xs,ys});
    while(!Q.empty()){
        int x,y; tie(x,y)=Q.front(); Q.pop();
        for(int k=0; k<4; k++){
            int u=x+dx[k], v=y+dy[k];
            if(B[u][v]=='D') return true;
            if(!valid(u,v) || D[u][v]>=0) continue;
            int now=D[x][y]+1;
            if(Y[u][v]>=0 && now>=Y[u][v]) continue;
            D[u][v]=D[x][y]+1;
            Q.push({u,v});
        }
    }
    return false;
    /*
    cout<<"\nSOLVED "<<t<<'\n';
    for(int i=1; i<=n; i++, cout<<'\n')
        for(int j=1; j<=n; j++)
            cout<<D[i][j]<<' ';
            */
}


int main(){
    ios::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>>B[i][j];
            if(B[i][j]=='M') xs=i, ys=j, B[i][j]='G';
            if(B[i][j]=='D') xl=i, yl=j;
        }
    bees();
    int s=0, e=n*n;
    while(s<e){
        int m=(s+e+1)/2;
        if(solve(m)) s=m;
        else e=m-1;
    }
    cout<<(solve(s) ? s : -1);
    return 0;
}

• Subtask 1: 100 / 100