Submission #1156015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156015		jakeob77	Mecho (IOI09_mecho)	C++17	84 / 100	181 ms	6176 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ins insert
//__builtin_popcount(x);
vector<pair<int,int>>dir={{-1,0},{1,0},{0,1},{0,-1}};//UDRL
const int mod=1e9+7;
int n,s;
char grid[801][801];
vector<vector<int>>bedist;
pair<int,int>mecho;
pair<int,int>dom;
bool good(int a,int b){
    if(a<0||a>=n) return false;
    if(b<0||b>=n) return false;
    if(grid[a][b]=='G'||grid[a][b]=='M') return true;
    else return false;
}
bool bear(int a,int b,int d){
    return (d/s<bedist[a][b]);
}
bool ok(int eat){
    vector<vector<int>>dist(n,vector<int>(n,mod));
    dist[mecho.first][mecho.second]=eat*s;
    queue<pair<int,int>>q;
    q.push({mecho.first,mecho.second});
    while(!q.empty()){
        auto cur=q.front();q.pop();
        for(int i=0;i<4;i++){
            int a=cur.first+dir[i].first,b=cur.second+dir[i].second;
            if(good(a,b)&&dist[a][b]>dist[a-dir[i].first][b-dir[i].second]+1&&bear(a,b,dist[a-dir[i].first][b-dir[i].second]+1)){
                dist[a][b]=dist[a-dir[i].first][b-dir[i].second]+1;
                q.push({a,b});
            }
        }
    }bool f=false;
    for(int i=0;i<4;i++){
        int a=dom.first+dir[i].first,b=dom.second+dir[i].second;
        if(good(a,b)&&dist[a][b]!=mod){
            f=true;break;
        }
    }
    return f;
}

void solve(){
    cin>>n>>s;
    vector<pair<int,int>>hives;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char c;cin>>c;
            grid[i][j]=c;
            if(c=='H'){
                hives.pb({i,j});
            }
            if(c=='M') mecho={i,j};
            if(c=='D') dom={i,j};
        }
    }
    bedist=vector<vector<int>>(n,vector<int>(n,mod));
    queue<pair<int,int>>q;
    for(int i=0;i<(int)hives.size();i++){
        q.push(hives[i]);
        bedist[hives[i].first][hives[i].second]=0;
    }
    while(!q.empty()){
        pair<int,int>cur=q.front();q.pop();
        for(int i=0;i<4;i++){
            if(good(cur.first+dir[i].first,cur.second+dir[i].second)&&bedist[cur.first][cur.second]+1<bedist[cur.first+dir[i].first][cur.second+dir[i].second]){
                bedist[cur.first+dir[i].first][cur.second+dir[i].second]=bedist[cur.first][cur.second]+1;
                q.push({cur.first+dir[i].first,cur.second+dir[i].second});
            }
        }
    }
    if(!ok(0)) {
        cout<<-1<<endl;
        return;
    }
    int l=0,r=n*n;
    while(l<r){
        int md=(l+r+1)/2;
        if(ok(md)){
            l=md;
        }
        else{
            r=md-1;
        }
    }
    cout<<l<<endl;
}

int main(){
    int t=1;
    while(t--) solve();
}

• Subtask 1: 84 / 100