Submission #1194687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194687		Hamed_Ghaffari	Mecho (IOI09_mecho)	C++20	100 / 100	145 ms	6216 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 803;
const int inf = 1e9;

int n, s;
char a[MXN][MXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int bee[MXN][MXN];

inline bool in(int i) {
    return 0<=i && i<n;
}

inline void bfs() {
    queue<pii> q;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(a[i][j]=='H') q.push({i,j});
            else bee[i][j] = inf;
    while(!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for(int d=0, x,y; d<4; d++) {
            x = i+dx[d];
            y = j+dy[d];
            if(in(x) && in(y) && a[x][y]!='T' && a[x][y]!='D' && bee[x][y]>bee[i][j]+1) {
                bee[x][y] = bee[i][j]+1;
                q.push({x, y});
            }
        }
    }
}

int dis[MXN][MXN];

inline bool check(int mid) {
    queue<pii> q;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(a[i][j]=='M') {
                if(bee[i][j]<=mid) return 0;
                dis[i][j] = mid*s;
                q.push({i, j});
            }
            else dis[i][j] = inf;
    while(!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for(int d=0,x,y; d<4; d++) {
            x = i+dx[d];
            y = j+dy[d];
            if(in(x) && in(y) && a[x][y]!='T' && dis[x][y]>dis[i][j]+1
            && bee[x][y]>(dis[i][j]+1)/s) {
                dis[x][y] = dis[i][j]+1;
                q.push({x, y});
            }
        }
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(a[i][j]=='D')
                return dis[i][j] != inf;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> s;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> a[i][j];
    bfs();
    int l=-1, r=n*n+23;
    while(r-l>1)
        (check(l+r>>1) ? l : r) = l+r>>1;
    cout << l << '\n';
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100