Submission #1312307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312307		klalnwza007	Mecho (IOI09_mecho)	C++17	100 / 100	139 ms	8532 KiB

mecho

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

int bee[810][810];
bool visbee[810][810];
int mhee[810][810];
bool vismhee[810][810];
string grid[810];

typedef pair<int,int> pii;
int di[] = {0,0,1,-1};
int dj[] = {1,-1,0,0};

pii st ,ed;

bool check(int delay, int n, int s) {
    auto [i,j] = st;
    if (visbee[i][j] && bee[i][j] <= delay) return false;

    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            vismhee[i][j] = false;
            mhee[i][j] = 0;
        }
    }

    queue<pii> q;
    q.push(st);
    vismhee[i][j] = true;

    while (!q.empty()) {
        auto [i,j] = q.front();
        q.pop();

        for (int k=0; k<4; k++) {
            int ni = i + di[k];
            int nj = j + dj[k];

            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (vismhee[ni][nj] || grid[ni][nj] == 'T') continue;

            if (grid[ni][nj] == 'D') return true;

            int mheet = delay + (mhee[i][j] + 1) / s;

            if (!visbee[ni][nj] || mheet < bee[ni][nj]) {
                mhee[ni][nj] = mhee[i][j] + 1;
                vismhee[ni][nj] = true;
                q.emplace(ni,nj);
            }
        }
    }
    return false;
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, s; cin >> n >> s;

    queue<pii> b;
    for (int i=0; i<n; i++) {
        cin >> grid[i];
        for (int j=0; j<n; j++) {
            if (grid[i][j] == 'H') {
                b.emplace(i,j);
                bee[i][j] = 0;
                visbee[i][j] = true;
            }
            if (grid[i][j] == 'M') st = {i, j};
            if (grid[i][j] == 'D') ed = {i, j};
        }
    }

    while (!b.empty()) {
        auto [i,j] = b.front();
        b.pop();

        for (int k=0; k<4; k++) {
            int ni = i + di[k], nj = j + dj[k];
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (visbee[ni][nj] || grid[ni][nj] == 'D' || grid[ni][nj] == 'T') continue;

            bee[ni][nj] = bee[i][j] + 1;
            visbee[ni][nj] = true;
            b.emplace(ni,nj);
        }
    }

    int l=0,r=n*n, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid, n, s)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans;
}

• Subtask 1: 100 / 100