Submission #928829

#	Time	Username	Problem	Language	Result	Execution time	Memory
928829		absolutePi	Mecho (IOI09_mecho)	C++17	95 / 100	503 ms	7200 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

const int N = 800;
int n,s;
int mx[]={1,-1,0,0},my[]={0,0,1,-1};
vector<vector<char>> grid(N,vector<char>(N));


bool valid_sit(int x,int y){
    return (x>=0&&y>=0&&x<n&&y<n&&(grid[x][y]=='G'||grid[x][y]=='M'));
}

bool mecho_reached(int m,int b){
    return (m/s)<b;
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin >> n >> s;
    vector<pair<int,int>> bees;
    pair<int,int> mecho,home;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> grid[i][j];
            if(grid[i][j]=='H'){
                bees.push_back({i,j});
            }
            if(grid[i][j]=='M'){
                mecho = {i,j};
            }
            if(grid[i][j]=='D'){
                home = {i,j};
            }
        }
    }
    int l=0,r=n*n;
    while(l<=r){
        vector<vector<bool>> visb(n,vector<bool>(n)),vism(n,vector<bool>(n));
        vector<vector<int>> distb(n,vector<int>(n)),distm(n,vector<int>(n));    
        queue<pair<int,int>> q;
        int eating_time=l+(r-l)/2;
        for(auto i : bees){
            q.push(i);
            visb[i.first][i.second]=true;
        }
        while(!q.empty()){
            int x,y;
            tie(x,y)=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int newx=x+mx[i];
                int newy=y+my[i];
                if(valid_sit(newx,newy)&&!visb[newx][newy]){
                    distb[newx][newy]=distb[x][y]+1;
                    q.push({newx,newy});
                    visb[newx][newy]=true;
                }
            }
        }
        q.push(mecho);
        vism[mecho.first][mecho.second]=true;
        if(distb[mecho.first][mecho.second]<=eating_time){q.pop();}
        while(!q.empty()){
            int x,y;
            tie(x,y)=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int newx=x+mx[i];
                int newy=y+my[i];
                if(valid_sit(newx,newy)&&!vism[newx][newy]&&(mecho_reached(distm[x][y]+1,distb[newx][newy]-eating_time))){
                    distm[newx][newy]=distm[x][y]+1;
                    q.push({newx,newy});
                    vism[newx][newy]=true;
                }
            }
        }
        bool reached=false;
        for(int i=0;i<4;i++){
            int newx=home.first+mx[i];
            int newy=home.second+my[i];
            if(valid_sit(newx,newy)&&vism[newx][newy]){
                reached=true;
            }
        }
        if(reached){
            l=eating_time+1;
        }
        else{
            r=eating_time-1;
        }
    }
    cout << l-1 << '\n';
}   

• Subtask 1: 95 / 100