Submission #1224110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224110		firegirlwaterboy	Mecho (IOI09_mecho)	C++20	34 / 100	519 ms	6828 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

int n, s;
vector<string> grid;

bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n &&
           (grid[x][y] == 'G' || grid[x][y] == 'M');
}

bool reached(int mdis, int bdis) { return mdis / s < bdis; }

int main() {
    cin >> n >> s;
    grid.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    vector<pii> hives;
    int mx, my, hx, hy;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 'M') {
                mx = i, my = j;
            } else if (grid[i][j] == 'H') {
                hives.push_back({i, j});
            } else if (grid[i][j] == 'D') {
                hx = i, hy = j;
            }
        }
    }
    auto ok = [&](int x) {
        vector<vector<bool>> bvis(n, vector<bool>(n)), mvis(n, vector<bool>(n));
        vector<vector<int>> btime(n, vector<int>(n)), mtime(n, vector<int>(n));
        queue<pii> q;
        for (auto i : hives) {
            q.push({i.first, i.second});
            bvis[i.first][i.second] = true;
        }
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (valid(nx, ny) && !bvis[nx][ny]) {
                    btime[nx][ny] = btime[x][y] + 1;
                    q.push({nx, ny});
                    bvis[nx][ny] = true;
                }
            }
        }
        q.push({mx, my});
        mvis[mx][my] = true;
        if (btime[mx][my] <= x) {
            q.pop();
        }
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (valid(nx, ny) && !mvis[nx][ny] &&
                    reached(mtime[x][y] + 1, btime[nx][ny] - x)) {
                    mvis[nx][ny] = true;
                    q.push({nx, ny});
                    mtime[nx][ny] = mtime[x][y] + 1;
                }
            }
        }
        bool tmp = false;
        for (int i = 0; i < 4; i++) {
            int nx = hx + dx[i], ny = hy + dy[i];
            if (valid(nx, ny) && reached(mtime[nx][ny], btime[nx][ny] - x) &&
                mvis[nx][ny]) {
                tmp = true;
            }
        }
        return tmp;
    };
    int l = 0, r = n * n, ans;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ok(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 34 / 100