Submission #571319

#	Time	Username	Problem	Language	Result	Execution time	Memory
571319		Vanilla	Mecho (IOI09_mecho)	C++17	21 / 100	345 ms	3836 KiB

mecho

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 801;
char a [maxn][maxn];
char c [maxn][maxn];
bool vis [maxn][maxn];
bool bad [maxn][maxn];
int n,s, sx, sy, ex, ey;
queue <pair <int, int> > startq;
int dx[] = {-1, 0, 1, -1};
int dy[] = {0, 1, 0, -1};

bool check (int minutes) {
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            vis[i][j] = 0;
            bad[i][j] = 0;
            c[i][j] = a[i][j];
        }
    }
    queue <pair <int, int> > bear, bee = startq;
    bear.push({sx, sy}); 
    // move bees for minutes before starting search
    while (minutes--) {
        int k = bee.size();
        for (int i = 0; i < k; i++){
            int x = bee.front().first, y = bee.front().second;
            bad[x][y] = 1;
            bee.pop();
            for (int j = 0; j < 4; j++){
                int nx = x + dx[j], ny = y + dy[j];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || bad[nx][ny] || 
                    c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
                c[nx][ny] = 'H';
                bad[nx][ny] = 1;
                bee.push({nx, ny});
            }
        }
    }
    while (!bear.empty()){
        for (int z = 0; z < s; z++){
            int k = bear.size();
            for (int i = 0; i < k; i++){
                int x = bear.front().first, y = bear.front().second;
                bear.pop();
                if (bad[x][y]) continue;
                for (int j = 0; j < 4; j++){
                    int nx = x + dx[j], ny = y + dy[j];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || 
                        c[nx][ny] == 'T' || c[nx][ny] == 'H') continue;
                    if (c[nx][ny] == 'D') return 1;
                    vis[nx][ny] = 1;
                    bear.push({nx, ny});
                }
            }
        }
        int k = bee.size();
        for (int i = 0; i < k; i++){
            int x = bee.front().first, y = bee.front().second;
            bad[x][y] = 1;
            bee.pop();
            for (int j = 0; j < 4; j++){
                int nx = x + dx[j], ny = y + dy[j];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || bad[nx][ny] || 
                    c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
                c[nx][ny] = 'H';
                bad[nx][ny] = 1;
                bee.push({nx, ny});
            }
        }
    }
    return 0;

}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        for (int j = 0; j < n; j++){
            if (a[i][j] == 'M') {
                sx = i, sy = j;
            }
            if (a[i][j] == 'D') {
                ex = i, ey = j;
            }
            if (a[i][j] == 'H') {
                startq.push({i,j});
            }
        }
    }
    // check(0);
    int l = 0, r = maxn * maxn, rs = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            rs = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    cout << rs;
    return 0;
}

• Subtask 1: 21 / 100