Submission #1194768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194768		nicolo_010	Mecho (IOI09_mecho)	C++20	24 / 100	444 ms	11396 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;
    while (!q.empty()) {
        int ni = q.front().first, nj = q.front().second;
        //cout << ni << " " << nj << "\n";
        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 && dis[x][y] == -1 && ((dis[ni][nj]+1)/S) < (grid[x][y] - m)) {
                dis[x][y] = dis[ni][nj] + 1;
                //if (m == 24) cout << dis[x][y] / S << " " << grid[x][y] - m << "\n";
                q.push({x, y});
            }
        }
    }
    bool can = false;
    rep(i, 0, n) {
        int x = end.first+dx[i];
        int y = end.second+dy[i];
        if (x >= 0 && y >= 0 && x < n && y < n && dis[x][y] != -1 && grid[x][y] != -1e9 && (dis[x][y]/S) < (grid[x][y] - m)) can = true;
    }
    return can;
}

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);
        /*
        if (m == 24) {
            for (auto x : aux) {
                for (auto y : x) {
                    cout << y << " ";
                }
                cout << endl;
            }
        }
        */
        //cout << m << " " << can << endl;
        if (can) {
            ans = m;
            l = m+1;
        }
        else r = m-1;
    }
    cout << ans << "\n";
}

• Subtask 1: 24 / 100