Submission #608803

#TimeUsernameProblemLanguageResultExecution timeMemory
608803MazaalaiMecho (IOI09_mecho)C++17
0 / 100
5 ms2904 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define ff first #define ss second #define LINE "---------------\n" #define sz(a) (int)a.size() using namespace std; using PII = pair <int, int>; const int N = 802; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; int n, m, X1, Y1, X2, Y2; vector <PII> hives; int mat[N][N], maze[N][N]; bool check(int lim) { memcpy(maze, mat, sizeof(mat)); queue <PII> bfs1, bfs2; for (auto& [a, b] : hives) bfs2.push({a, b}); for (int i = 0; i < lim; i++) { int rep = sz(bfs2); for (int j = 0; j < rep; j++) { int x, y; tie(x, y) = bfs2.front(); bfs2.pop(); for (int a = 0; a < 4; a++) { int xx = dx[a] + x; int yy = dy[a] + y; if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] != 0) continue; maze[xx][yy] = 1; bfs2.push({xx, yy}); } } } if (maze[X1][Y1] == 1) return 0; maze[X1][Y1] = 2; bfs1.push({X1, Y1}); bool changed = 1; // cout << "START\n"; // cout << lim << '\n'; // for (int i = 1; i <= n; i++) // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n]; while (maze[X2][Y2] == 4 && changed) { // move bear changed = 0; for (int i = 0; i < m; i++) { int rep = sz(bfs1); for (int j = 0; j < rep; j++) { int x, y; tie(x, y) = bfs1.front(); bfs1.pop(); if (maze[x][y] == 1) continue; for (int a = 0; a < 4; a++) { int xx = dx[a] + x; int yy = dy[a] + y; if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] == 1 || maze[xx][yy] == 2) continue; changed = 1; maze[xx][yy] = 2; bfs1.push({xx, yy}); } } } if (maze[X2][Y2] != 4) return 1; // spread bees int rep = sz(bfs2); for (int j = 0; j < rep; j++) { int x, y; tie(x, y) = bfs2.front(); bfs2.pop(); for (int a = 0; a < 4; a++) { int xx = dx[a] + x; int yy = dy[a] + y; if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] == 1 || maze[xx][yy] == 4) continue; changed = 1; maze[xx][yy] = 1; bfs2.push({xx, yy}); } } // cout << LINE; // for (int i = 1; i <= n; i++) // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n]; } return 0; } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); freopen("0.in", "r", stdin); freopen("0.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { char x; cin >> x; if (x == 'T') { // tree mat[i][j] = 1; } else if (x == 'G') { // grass mat[i][j] = 0; } else if (x == 'M') { // mecho the bear tie(X1, Y1) = mp(i, j); mat[i][j] = 0; } else if (x == 'D') { // home of the mecho mat[i][j] = 4; tie(X2, Y2) = mp(i, j); } else if (x == 'H') { // bee hive mat[i][j] = 1; hives.pb({i, j}); } } int l = 0, r = n*n/2, ans = -1; while (l <= r) { int m = (l+r)>>1; if (check(m)) { l = m+1; ans = m; } else { r = m-1; } } cout << ans << "\n"; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     freopen("0.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen("0.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...