Submission #337423

#	Time	Username	Problem	Language	Result	Execution time	Memory
337423		arbor	Mecho (IOI09_mecho)	C++17	100 / 100	183 ms	7020 KiB

mecho

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 805;
int N, S, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
char a[MN][MN];
int bee[MN][MN], dis[MN][MN];
int sx, sy, ex, ey;

bool good(int t) {
    if (t >= bee[sx][sy]) return false;
    memset(dis, 0x3f, sizeof(dis));
    dis[sx][sy] = t + 1;
    queue<pair<pii, int>> q;
    q.push({{sx, sy}, S});
    while (!q.empty()) {
        auto [p, s] = q.front(); q.pop();
        auto [x, y] = p;
        if (!s && dis[x][y] >= bee[x][y]) continue;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > N || ny < 1 || ny > N || a[nx][ny] == 'T') continue;
            if (!s) {
                int nd = dis[x][y] + 1;
                if (dis[nx][ny] > nd && nd <= bee[nx][ny]) {
                    dis[nx][ny] = nd;
                    q.push({{nx, ny}, S - 1});
                }
            } else {
                int nd = dis[x][y];
                if (dis[nx][ny] > nd && nd <= bee[nx][ny]) {
                    dis[nx][ny] = nd;
                    q.push({{nx, ny}, s - 1});
                }
            }
        }
    }
    return dis[ex][ey] < 1e9;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> S;
    queue<pii> q;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            cin >> a[i][j];
            bee[i][j] = 1e9;
            if (a[i][j] == 'M') sx = i, sy = j;
            if (a[i][j] == 'D') ex = i, ey = j;
            if (a[i][j] == 'H') q.emplace(i, j), bee[i][j] = 0;
        }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > N || ny < 1 || ny > N || a[nx][ny] == 'T' || a[nx][ny] == 'D') continue;
            if (bee[nx][ny] > bee[x][y] + 1) bee[nx][ny] = bee[x][y] + 1, q.emplace(nx, ny);
        }
    }
    int l = 0, r = 5e5;
    while (l < r) {
        int m = (l + r) / 2;
        if (!good(m)) r = m;
        else l = m + 1;
    }
    cout << l - 1 << '\n';
    return 0;
}

• Subtask 1: 100 / 100