Submission #950874

#	Time	Username	Problem	Language	Result	Execution time	Memory
950874		blackslex	Mecho (IOI09_mecho)	C++17	84 / 100	141 ms	6720 KiB

mecho

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using tp = tuple<int, int, int>;

const int cd[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int n, s, sx, sy, tx, ty;

int main() {
    scanf("%d %d", &n, &s);
    vector<string> c(n + 5);
    for (int i = 1; i <= n; i++) cin >> c[i], c[i] = " " + c[i];
    queue<pii> q;
    vector<vector<int>> d(n + 5, vector<int>(n + 5, 1e9));
    vector<vector<bool>> f(n + 5, vector<bool>(n + 5));
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (c[i][j] == 'M') sx = i, sy = j; else if (c[i][j] == 'H') d[i][j] = 1, q.emplace(i, j); else if (c[i][j] == 'D') tx = i, ty = j;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (f[x][y]) continue; f[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + cd[i][0], ny = y + cd[i][1];
            if (nx <= 0 || nx > n || ny <= 0 || ny > n || c[nx][ny] == 'T' || c[nx][ny] == 'D') continue;
            if (d[nx][ny] > d[x][y] + 1) d[nx][ny] = d[x][y] + 1, q.emplace(nx, ny);
        }
    }
    auto bs = [&] (int val) {
        vector<vector<int>> d2(n + 5, vector<int>(n + 5, 1e9));
        vector<vector<bool>> f2(n + 5, vector<bool>(n + 5));
        queue<tp> cq; d2[sx][sy] = val + 1; cq.emplace(sx, sy, 0);
        while (!cq.empty()) {
            auto [x, y, t] = cq.front(); cq.pop();
            if (f2[x][y]) continue; f2[x][y] = 1;
            int nt = t + 1, nts = (t + 1) % s;
            for (int i = 0; i < 4; i++) {
                int nx = x + cd[i][0], ny = y + cd[i][1];
                if (nx <= 0 || nx > n || ny <= 0 || ny > n || c[nx][ny] == 'T' || f2[nx][ny]) continue;
                if (!nts) d2[nx][ny] = d2[x][y] + 1;
                else d2[nx][ny] = d2[x][y];
                if (d2[nx][ny] < d[nx][ny]) cq.emplace(nx, ny, nt);
            }
        }
        return d2[tx][ty] != 1e9;
    };
    int l = 0, r = 1e6;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (bs(mid)) l = mid + 1;
        else r = mid - 1;
    }
    printf("%d", r);
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:20:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |         if (f[x][y]) continue; f[x][y] = 1;
      |         ^~
mecho.cpp:20:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |         if (f[x][y]) continue; f[x][y] = 1;
      |                                ^
mecho.cpp: In lambda function:
mecho.cpp:33:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |             if (f2[x][y]) continue; f2[x][y] = 1;
      |             ^~
mecho.cpp:33:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |             if (f2[x][y]) continue; f2[x][y] = 1;
      |                                     ^~
mecho.cpp: In function 'int main()':
mecho.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d", &n, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 84 / 100