Submission #848164

#	Time	Username	Problem	Language	Result	Execution time	Memory
848164		uped	Mecho (IOI09_mecho)	C++14	100 / 100	199 ms	6368 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

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

char f[max_n][max_n];
int mt[max_n][max_n];
int n, s;
pair<int, int> start;

bool inside(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < n && f[i][j] != 'T';
}

bool check(int offset) {
    queue<pair<int, int>> q;
    vector<vector<int>> ms(n, vector<int>(n, 10e7));
    ms[start.first][start.second] = 0;
    q.emplace(start.first, start.second);

    if (mt[start.first][start.second] <= offset) {
        return false;
    }

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (!inside(ni, nj)) continue;
            if (f[ni][nj] == 'D') {
                return true;
            }
            int steps = ms[i][j] + 1;
            bool possible = offset + (steps / s) < mt[ni][nj];
            if (possible && steps < ms[ni][nj]) {
                ms[ni][nj] = steps;
                q.emplace(ni, nj);
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            mt[i][j] = 10e7;
        }
    }
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> f[i][j];
            if (f[i][j] == 'M') {
                start = {i, j};
            } else if (f[i][j] == 'H') {
                q.emplace(i, j);
                mt[i][j] = 0;
            }
        }
    }

    // make mt
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (!inside(ni, nj) || f[ni][nj] == 'D') continue;
            if (mt[i][j] + 1 < mt[ni][nj]) {
                mt[ni][nj] = mt[i][j] + 1;
                q.emplace(ni, nj);
            }
        }
    }
    if (!check(0)) {
        cout << -1;
        return 0;
    }

    int l = 0, r = 640000;
    while (r > l + 1) {
        int mid = (r + l) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l;
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [i, j] = q.front();
      |              ^
mecho.cpp: In function 'int main()':
mecho.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |         auto [i, j] = q.front();
      |              ^

• Subtask 1: 100 / 100