Submission #770997

#TimeUsernameProblemLanguageResultExecution timeMemory
770997ind1vMecho (IOI09_mecho)C++11
38 / 100
149 ms7548 KiB
#include <bits/stdc++.h> using namespace std; const int N = 805; const int dI[4] = {-1, 0, +1, 0}; const int dJ[4] = {0, +1, 0, -1}; int n, s; char a[N][N]; int d[N][N], f[N][N]; bool can[N][N]; int mx, my, dx, dy; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> s; memset(d, 0x3f, sizeof(d)); memset(f, 0x3f, sizeof(f)); queue<pair<int, int>> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; if (a[i][j] == 'H') { d[i][j] = 0; q.push({i, j}); } else if (a[i][j] == 'M') { mx = i; my = j; } else if (a[i][j] == 'D') { dx = i; dy = j; } } } while (!q.empty()) { int x, y; tie(x, y) = q.front(); q.pop(); for (int dir = 0; dir < 4; dir++) { int nx = x + dI[dir]; int ny = y + dJ[dir]; if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'D' && a[nx][ny] != 'T' && d[nx][ny] > d[x][y] + 1) { d[nx][ny] = d[x][y] + 1; q.push({nx, ny}); } } } int l = 0, r = n * n, ans = -1; while (l <= r) { int m = l + r >> 1; memset(f, 0x3f, sizeof(f)); memset(can, false, sizeof(can)); queue<pair<int, int>> q; if (m <= d[mx][my]) { f[mx][my] = s; can[mx][my] = true; q.push({mx, my}); } while (!q.empty()) { int x, y; tie(x, y) = q.front(); q.pop(); for (int dir = 0; dir < 4; dir++) { int nx = x + dI[dir]; int ny = y + dJ[dir]; if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'T' && f[nx][ny] > f[x][y] + 1 && f[x][y] / s + m <= d[nx][ny] && !can[nx][ny]) { f[nx][ny] = f[x][y] + 1; can[nx][ny] = true; q.push({nx, ny}); } } } if (can[dx][dy]) { ans = m; l = m + 1; } else { r = m - 1; } } cout << ans; return 0; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int m = l + r >> 1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...