Submission #1202964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202964		nathlol2	Mecho (IOI09_mecho)	C++20	100 / 100	257 ms	2760 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
const int mxN = 800;
int n, k;
string tb[mxN];
bool mvis[mxN][mxN];
bool bvis[mxN][mxN];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool ok(int x){
    memset(mvis, 0, sizeof mvis);
    memset(bvis, 0, sizeof bvis);
    int ex, ey;
    queue<pair<int, int>> q1, q2, b1, b2;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(tb[i][j] == 'M'){
                b1.push({i, j});
                mvis[i][j] = 1;
            }else if(tb[i][j] == 'H'){
                q1.push({i, j});
                bvis[i][j] = 1;
            }else if(tb[i][j] == 'D'){
                ex = i;
                ey = j;
            }
        }
    }
    for(int i = 0;i<x;i++){
        while(!q1.empty()){
            auto [x, y] = q1.front();
            q1.pop();
            for(int j = 0;j<4;j++){
                int nx = x + dx[j];
                int ny = y + dy[j];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n || bvis[nx][ny] || tb[nx][ny] == 'T' || tb[nx][ny] == 'D') continue;
                bvis[nx][ny] = 1;
                q2.push({nx, ny});
            }
        }
        swap(q1, q2);
    }
    while(1){
        auto [x, y] = b1.front();
        if(bvis[x][y]){
            return false;
        }
        break;
    }
    while(!b1.empty()){
        for(int i = 0;i<k;i++){
            while(!b1.empty()){
                auto [x, y] = b1.front();
                b1.pop();
                if(bvis[x][y]) continue;
                for(int j = 0;j<4;j++){
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= n || bvis[nx][ny] || mvis[nx][ny] || tb[nx][ny] == 'T') continue;
                    mvis[nx][ny] = 1;
                    b2.push({nx, ny});
                }
            }
            swap(b1, b2);
        }
        while(!q1.empty()){
            auto [x, y] = q1.front();
            q1.pop();
            for(int j = 0;j<4;j++){
                int nx = x + dx[j];
                int ny = y + dy[j];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n || bvis[nx][ny] || tb[nx][ny] == 'T' || tb[nx][ny] == 'D') continue;
                bvis[nx][ny] = 1;
                q2.push({nx, ny});
            }
        }
        swap(q1, q2);
    }
    return mvis[ex][ey];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i = 0;i<n;i++){
        cin >> tb[i];
    }
    int l = 0, r = n * n + 1, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ok(mid)){
            l = mid + 1;
            ans = mid;
        }else{
            r = mid - 1;
        }
    }
    cout << ans;
}

• Subtask 1: 100 / 100