Submission #777107

#	Time	Username	Problem	Language	Result	Execution time	Memory
777107		Surver	Mecho (IOI09_mecho)	C++17	100 / 100	201 ms	11496 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n,s;
    cin>>n>>s;
    vector<string> v(n);
    for (int i=0;i<n;i++){
        cin>>v[i];
    }   
    int inf=(int)1e12;
    vector<vector<int>> dis(n,vector<int>(n,inf));
    queue<pair<int,int>> q;
    pair<int,int> start={-1,-1};
    pair<int,int> end={-1,-1};
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (v[i][j]=='H'){
                q.push({i,j});
                dis[i][j]=0;
            }
            if (v[i][j]=='M'){
                start={i,j};
            }
            if (v[i][j]=='D'){
                end={i,j};
            }
        }
    }
    auto valid = [&] (int x,int y){
        return x>=0 && x<n && y>=0 && y<n;
    };
    vector<int> dx={0,-1,0,1};
    vector<int> dy={-1,0,1,0};
    while(!q.empty()){
        auto [x,y]=q.front();
        q.pop();
        for (int i=0;i<4;i++){
            if (valid(x+dx[i],y+dy[i]) && dis[x+dx[i]][y+dy[i]]==inf){
                if (v[x+dx[i]][y+dy[i]]=='G'){
                    dis[x+dx[i]][y+dy[i]]=1+dis[x][y];
                    q.push({x+dx[i],y+dy[i]});
                }
                if (v[x+dx[i]][y+dy[i]]=='M'){
                    dis[x+dx[i]][y+dy[i]]=1+dis[x][y];
                }
            }
        }
    }
    int low=0,high=inf;
    int ans=-1;
    while(low<=high){
        int mid=(low+high)/2;
        vector<vector<int>> dis2(n,vector<int>(n,inf));
        q.push(start);
        if (mid>=dis[start.first][start.second]){
            q.pop();
        }
        dis2[start.first][start.second]=mid*s;
        while(!q.empty()){
            auto [x,y]=q.front();
            q.pop();
            for (int i=0;i<4;i++){
                if (valid(x+dx[i],y+dy[i]) && v[x+dx[i]][y+dy[i]]!='T'){
                    if ((dis2[x][y]+1)/s<dis[x+dx[i]][y+dy[i]] && dis2[x+dx[i]][y+dy[i]]==inf){
                        dis2[x+dx[i]][y+dy[i]]=1+dis2[x][y];
                        q.push({x+dx[i],y+dy[i]});
                    }
                }
            }
        }
        if (dis2[end.first][end.second]==inf){
            high=mid-1;
        }
        else{
            ans=max(ans,mid);
            low=mid+1;
        }
    }
    cout<<ans<<"\n";
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100