Submission #1018393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018393		cryptobunny	Mecho (IOI09_mecho)	C++14	29 / 100	491 ms	18584 KiB

mecho

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

#define int long long

int n, s, mx, my;

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

bool check(int t, vector<vector<char>> grid, vector<vector<int>> btime) {
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({0, {mx, my}});
    vector<vector<int>> dist(n, vector<int>(n, 0x3f3f3f3f));
    dist[mx][my] = 0;
    while (!q.empty()) {
        auto tp = q.top();
        q.pop();
        if (grid[tp.second.first][tp.second.second] == 'D') {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + tp.second.first;
            int ny = dy[i] + tp.second.second;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] == 'T' || (btime[nx][ny] - t) * s <= -tp.first) continue;
            if (dist[nx][ny] > 1 - tp.first) {
                dist[nx][ny] = 1 - tp.first;
                q.push({tp.first - 1, {nx, ny}});
            }
        }
    }
    return false;
}

signed main() {
    cin >> n >> s;
    vector<vector<char>> grid(n, vector<char>(n));
    priority_queue<pair<int, pair<int, int>>> q;
    vector<vector<int>> btime(n, vector<int>(n, 0x3f3f3f3f));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'H') {
                btime[i][j] = 0;
                q.push({0, {i, j}});
            }
            if (grid[i][j] == 'M') mx = i, my = j;
        }
    }
    while (!q.empty()) {
        auto tp = q.top();
        q.pop();
        if (btime[tp.second.first][tp.second.second] != -tp.first) continue;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + tp.second.first;
            int ny = dy[i] + tp.second.second;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] != 'G' && grid[nx][ny] != 'M') continue;
            if (-tp.first + 1 < btime[nx][ny]) {
                btime[nx][ny] = 1 - tp.first;
                q.push({-1 + tp.first, {nx, ny}});
            }
        }
    }

    int l = 0;
    int r = 1e9 + 1;
    while (l != r) {
        int mid = (l + r + 1)/2;
        if (check(mid, grid, btime)) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    cout << l << endl;
}

• Subtask 1: 29 / 100