Submission #1238805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238805		gramathegod	Mecho (IOI09_mecho)	C++20	100 / 100	136 ms	6216 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

const int N=805;

int di[4]={0,0,1,-1};
int dj[4]={1,-1,0,0};

int n,s;

char v[N][N];

int mecho[N][N], bees[N][N];

bool check(int i, int j){
    return 0<=i && i<n && 0<=j && j<n;
}

pair<int, int>start,finish;

bool verif(int x){
    memset(mecho, (1<<6)-1, sizeof(mecho));
    queue<pair<int, int>> q;
    q.push(start);
    mecho[start.first][start.second]=x*s;
    if (x>=bees[start.first][start.second]){
        return false;
    }
    while (!q.empty()){
        auto z=q.front();q.pop();
        int i=z.first;
        int j=z.second;
        int d=mecho[i][j]+1;
        int t=d/s;
        for (int k=0;k<4;k++){
            int newi=i+di[k];
            int newj=j+dj[k];
            if (check(newi, newj) && (v[newi][newj]=='G') && mecho[newi][newj]>d && bees[newi][newj]>t){
                mecho[newi][newj]=d;
                q.push({newi, newj});
            }
        }
    }
    /*if (x<3){
        cout<<x<<endl;
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (mecho[i][j]>1e9){
                    cout<<-1;
                }
                else{
                    if (mecho[i][j]>9){
                        cout<<mecho[i][j];
                    }
                    else{
                        cout<<' '<<mecho[i][j];
                    }
                }
                cout<<' ';
            }
            cout<<'\n';
        }
    }*/
    int i=finish.first;
    int j=finish.second;
    for (int k=0;k<4;k++){
        int newi=i+di[k];
        int newj=j+dj[k];
        if (check(newi, newj) && mecho[newi][newj]<1e9){
            int d=mecho[newi][newj];
            int t=d/s;
            if (d%s==0 && bees[newi][newj]==t){//is the last move of that second and the bees catch him
                continue;
            }
            if (bees[newi][newj]>t){//he still has at least one move in that second and can reach the home safely
                mecho[i][j]=d+1;
            }
        }
    }
    if (mecho[i][j]<1e9){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    //freopen("input.in", "r", stdin);
    #endif // ONLINE_JUDGE
    memset(bees, (1<<6)-1, sizeof(bees));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>s;
    queue<pair<int, int>> q;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin>>v[i][j];
            if (v[i][j]=='M'){
                start={i,j};
                v[i][j]='G';
            }
            else if (v[i][j]=='H'){
                bees[i][j]=0;
                q.push({i,j});
            }
            else if (v[i][j]=='D'){
                finish={i,j};
            }
        }
    }
    while (!q.empty()){
        auto z=q.front();q.pop();
        int i=z.first;
        int j=z.second;
        int d=bees[i][j];
        for (int k=0;k<4;k++){
            int newi=i+di[k];
            int newj=j+dj[k];
            if (check(newi, newj) && v[newi][newj]=='G' && bees[newi][newj]>d+1){
                bees[newi][newj]=d+1;
                q.push({newi, newj});
            }
        }
    }
    /*for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (bees[i][j]>1e9){
                cout<<-1;
            }
            else{
                if (bees[i][j]>9){
                    cout<<bees[i][j];
                }
                else{
                    cout<<' '<<bees[i][j];
                }
            }
            cout<<' ';
        }
        cout<<'\n';
    }*/
    int left=0, right=n*n;
    int ans=-1;
    while (left<=right){
        int mid=(left+right)/2;
        if (verif(mid)){
            ans=mid;
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    cout<<ans;
}

• Subtask 1: 100 / 100