Submission #1194762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194762		nicolo_010	Mecho (IOI09_mecho)	C++20	25 / 100	353 ms	11404 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

v<int> dx = {1, 0, -1, 0};
v<int> dy = {0, 1, 0, -1};

bool bfs(v<v<int>> &grid, pii idx, pii end, int S, int m) {
    queue<pii> q;
    int n = grid.size();
    q.push(idx);
    v<v<int>> dis(n, v<int> (n, -1));
    dis[idx.first][idx.second] = 0;
    if (grid[idx.first][idx.second] >= m) return false;
    while (!q.empty()) {
        int ni = q.front().first, nj = q.front().second;
        //cout << ni << " " << nj << "\n";
        q.pop();
        if (ni == end.first && nj == end.second) return true;
        rep(i, 0, 4) {
            int x = ni + dx[i];
            int y = nj + dy[i];
            if (x >= 0 && y >= 0 && x < n && y < n && dis[x][y] == -1 && ((dis[ni][nj]+1)/S + m) < grid[x][y]) {
                dis[x][y] = dis[ni][nj] + 1;
                q.push({x, y});
            }
        }
    }
    return false;
}

int main() {
    int n, s; cin >> n >> s;
    v<string> grid(n);
    rep(i, 0, n) {
        cin >> grid[i];
    }
    v<v<int>> dis(n, v<int> (n, -1));
    pii idx;
    pii end;
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (grid[i][j] == 'M') idx = {i, j};
            if (grid[i][j] == 'D') end = {i, j};
        }
    }
    int l = -1, r = n*n;
    int ans;
    while (l <= r) {
        int m = (l+r) / 2;
        v<v<int>> aux(n, v<int>(n));
        v<v<int>> dis(n, v<int> (n, -2));
        queue<pii> q;
        rep(i, 0, n) {
            rep(j, 0, n) {
                if (grid[i][j] == 'T') aux[i][j] = -1e9;
                if (grid[i][j] == 'H') {
                    aux[i][j] = -1e9;
                    q.push({i, j});
                    dis[i][j] = -1;
                }
                if (grid[i][j] == 'G' || grid[i][j] == 'D') aux[i][j] = 1e9;
            }
        }
        while (!q.empty()) {
            int ni = q.front().first, nj = q.front().second;
            q.pop();
            rep(i, 0, 4) {
                int x = ni + dx[i];
                int y = nj + dy[i];
                if (x >= 0 && y >= 0 && x < n && y < n && (grid[x][y] == 'G' || grid[x][y] == 'M') && dis[x][y] == -2 && dis[ni][nj] + 1 <= m) {
                    dis[x][y] = dis[ni][nj] + 1;
                    aux[x][y] = dis[x][y];
                    q.push({x, y});
                }
            }
        }
        bool can = bfs(aux, idx, end, s, m);
        //cout << m << " " << can << endl;
        if (can) {
            ans = m;
            l = m+1;
        }
        else r = m-1;
    }
    cout << ans << "\n";
}

• Subtask 1: 25 / 100