Submission #1270045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270045		BlockOG	Mecho (IOI09_mecho)	C++20	84 / 100	1094 ms	4424 KiB

mecho

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

int n, s;
pair<int, int> start, eend;

bool walls[800][800];
bool been[800][800];
int dist[800][800];

bool check(int t) {
    queue<pair<int, pair<int, int>>> q;
    q.push({t, start});
    while (q.size()) {
        auto [d, p] = q.front();
        auto [i, j] = p;
        q.pop();

        if (d >= dist[i][j]) continue;
        if (eend.f == i && eend.s == j) return true;

        if (0 < i && !been[i - 1][j]) {
            been[i - 1][j] = true;
            q.push({d + 1, {i - 1, j}});
        }
        if (0 < j && !been[i][j - 1]) {
            been[i][j - 1] = true;
            q.push({d + 1, {i, j - 1}});
        }
        if (i < n - 1 && !been[i + 1][j]) {
            been[i + 1][j] = true;
            q.push({d + 1, {i + 1, j}});
        }
        if (j < n - 1 && !been[i][j + 1]) {
            been[i][j + 1] = true;
            q.push({d + 1, {i, j + 1}});
        }
    }

    return false;
}

int main() {
    cin >> n >> s;

    {
        queue<pair<int, pair<int, int>>> q;
        fo(i, 0, n) {
            string a;
            cin >> a;
            fo(j, 0, n) {
                walls[i][j] = been[i][j] = a[j] != 'G';
                if (a[j] == 'H') q.push({0, {i, j}});
                if (a[j] == 'M') start = {i, j};
                if (a[j] == 'D') eend = {i, j};
            }
        }

        while (q.size()) {
            auto [d, p] = q.front();
            auto [i, j] = p;
            q.pop();

            if (0 < i && !been[i - 1][j]) {
                been[i - 1][j] = true;
                dist[i - 1][j] = d + s;
                q.push({d + s, {i - 1, j}});
            }
            if (0 < j && !been[i][j - 1]) {
                been[i][j - 1] = true;
                dist[i][j - 1] = d + s;
                q.push({d + s, {i, j - 1}});
            }
            if (i < n - 1 && !been[i + 1][j]) {
                been[i + 1][j] = true;
                dist[i + 1][j] = d + s;
                q.push({d + s, {i + 1, j}});
            }
            if (j < n - 1 && !been[i][j + 1]) {
                been[i][j + 1] = true;
                dist[i][j + 1] = d + s;
                q.push({d + s, {i, j + 1}});
            }
        }
    }

    dist[start.f][start.s] = 2000000000;
    dist[eend.f][eend.s] = 2000000000;
    walls[eend.f][eend.s] = false;

    int l = -s, r = 2000000000;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        fo(i, 0, n) fo(j, 0, n) been[i][j] = walls[i][j];
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l / s << endl;
}

• Subtask 1: 84 / 100