Submission #851506

#	Time	Username	Problem	Language	Result	Execution time	Memory
851506		abcvuitunggio	Mecho (IOI09_mecho)	C++17	100 / 100	154 ms	11856 KiB

mecho

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},d[801][801],d2[801][801];
string m[801];
queue <pair <int, int>> q;
bool check(int x){
    memset(d2,0,sizeof(d2));
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (m[i][j]=='M'){
                if (d[i][j]<=x*s)
                    return false;
                q.push({i,j});
                d2[i][j]=1;
            }
    while (!q.empty()){
        auto [i,j]=q.front();
        q.pop();
        for (int k=0;k<4;k++){
            int u=i+dx[k],v=j+dy[k];
            if (min(u,v)>=0&&max(u,v)<n)
                if (m[u][v]!='T'&&d[u][v]-x*s>d2[i][j]&&!d2[u][v]){
                    d2[u][v]=d2[i][j]+1;
                    q.push({u,v});
                }
        }
    }
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (m[i][j]=='D')
                return d2[i][j];
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> s;
    for (int i=0;i<n;i++){
        cin >> m[i];
        for (int j=0;j<n;j++)
            if (m[i][j]=='H'){
                q.push({i,j});
                d[i][j]=1;
            }
    }
    while (!q.empty()){
        auto [i,j]=q.front();
        q.pop();
        for (int k=0;k<4;k++){
            int u=i+dx[k],v=j+dy[k];
            if (min(u,v)>=0&&max(u,v)<n)
                if (m[u][v]!='T'&&m[u][v]!='D'&&!d[u][v]){
                    d[u][v]=d[i][j]+1;
                    q.push({u,v});
                }
        }
    }
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            d[i][j]=(d[i][j]?(d[i][j]-1)*s:1e18);
    int l=0,r=1e9,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        if (check(mid)){
            kq=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    cout << kq;
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(long long int)':
mecho.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

• Subtask 1: 100 / 100