Submission #572133

#TimeUsernameProblemLanguageResultExecution timeMemory
572133VanillaMecho (IOI09_mecho)C++17
21 / 100
308 ms3200 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 810; char a [maxn][maxn]; char c [maxn][maxn]; bool vis [maxn][maxn]; bool bad [maxn][maxn]; int n,s, sx, sy, ex, ey; queue <pair <int, int> > startq; int dx[] = {-1, 0, 1, -1}; int dy[] = {0, 1, 0, -1}; void propagate_bees(queue <pair <int, int> > &bee) { int k = bee.size(); for (int i = 0; i < k; i++){ int x = bee.front().first, y = bee.front().second; bee.pop(); for (int j = 0; j < 4; j++){ int nx = x + dx[j], ny = y + dy[j]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue; c[nx][ny] = 'H'; bee.push({nx, ny}); } } } bool check (int minutes) { for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ vis[i][j] = 0; c[i][j] = a[i][j]; } } queue <pair <int, int> > bear, bee = startq; bear.push({sx, sy}); // move bees for minutes before starting search while (minutes--) { propagate_bees(bee); } while (!bear.empty()){ for (int z = 0; z < s; z++){ int k = bear.size(); for (int i = 0; i < k; i++){ int x = bear.front().first, y = bear.front().second; bear.pop(); if (c[x][y] == 'H') continue; for (int j = 0; j < 4; j++){ int nx = x + dx[j], ny = y + dy[j]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || c[nx][ny] == 'T' || c[nx][ny] == 'H') continue; if (c[nx][ny] == 'D') return 1; vis[nx][ny] = 1; bear.push({nx, ny}); } } } int k = bee.size(); propagate_bees(bee); } return 0; } int main() { cin >> n >> s; for (int i = 0; i < n; i++){ cin >> a[i]; for (int j = 0; j < n; j++){ if (a[i][j] == 'M') { sx = i, sy = j; a[i][j] = 'G'; } if (a[i][j] == 'D') { ex = i, ey = j; } if (a[i][j] == 'H') { startq.push({i,j}); } } } // check(0); int l = 0, r = maxn * maxn, rs = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { rs = mid; l = mid + 1; } else { r = mid - 1; } } cout << rs; return 0; }

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:59:13: warning: unused variable 'k' [-Wunused-variable]
   59 |         int k = bee.size();
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...