Submission #1175668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175668		nagornz	Mecho (IOI09_mecho)	C++20	30 / 100	130 ms	21576 KiB

mecho

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math,unsafe-math-optimizations")
#define int long long
#define f first
#define s second
#define pii pair <int, int>
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define emb emplace_back

using namespace std;

const int inf = 1e14;
const int mod = 998244353;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

bool can(int n, int sx, int sy, int ex, int ey, vector <vector <int>> &bee, vector <vector <int>> &bear, int mid) {
    queue <pii> q; q.emplace(sx, sy);
    vector <vector <bool>> visited(n, vector <bool> (n));
    visited[sx][sy] = 1;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] || bee[nx][ny] <= bear[nx][ny] + mid) continue;
            if (nx == ex && ny == ey) return true;
            q.emplace(nx, ny);
            visited[nx][ny] = 1;
        }
    }
    return false;
}

int32_t main(){
    iShowSpeed;
    int n, k; cin >> n >> k;
    char a[n][n];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
    vector <vector <int>> bee(n, vector <int> (n, inf)), bear(n, vector <int> (n, inf));
    vector <vector <pii>> prev(n, vector <pii> (n, {-1, -1}));
    queue <pii> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'H') bee[i][j] = 0, q.emplace(i, j);
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || bee[nx][ny] <= bee[x][y] + 1) continue;
            q.emplace(nx, ny);
            bee[nx][ny] = bee[x][y] + 1;
        }
    }
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'M') bear[i][j] = 0, q.emplace(i, j), sx = i, sy = j;
            if (a[i][j] == 'D') ex = i, ey = j;
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || bear[nx][ny] <= bear[x][y] + 1) continue;
            q.emplace(nx, ny);
            bear[nx][ny] = bear[x][y] + 1;
            prev[nx][ny] = {x, y};
        }
    }
    // for (auto [x, y] : path) cout << x << " " << y << "\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            bear[i][j] = (bear[i][j] + k - 1) / k;
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << bee[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "--------------------\n";
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << bear[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "--------------------\n";
    int ans = -1;
    int l = 0, r = inf;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (can(n, sx, sy, ex, ey, bee, bear, mid)) {
            l = mid + 1;
            ans = max(ans, mid);
        }
        else r = mid - 1;
    }
    cout << ans;
}

• Subtask 1: 30 / 100