Submission #1175655

#TimeUsernameProblemLanguageResultExecution timeMemory
1175655nagornzMecho (IOI09_mecho)C++20
6 / 100
55 ms21576 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops,fast-math,unsafe-math-optimizations") #define int long long #define f first #define s second #define pii pair <int, int> #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) #define emb emplace_back using namespace std; const int inf = 1e14; const int mod = 998244353; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int32_t main(){ iShowSpeed; int n, k; cin >> n >> k; char a[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j]; vector <vector <int>> bee(n, vector <int> (n, inf)), bear(n, vector <int> (n, inf)); vector <vector <pii>> prev(n, vector <pii> (n, {-1, -1})); queue <pii> q; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 'H') bee[i][j] = 0, q.emplace(i, j); } } while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || bee[nx][ny] <= bee[x][y] + 1) continue; q.emplace(nx, ny); bee[nx][ny] = bee[x][y] + 1; } } int ex, ey; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 'M') bear[i][j] = 0, q.emplace(i, j); if (a[i][j] == 'D') ex = i, ey = j; } } while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || bear[nx][ny] <= bear[x][y] + 1) continue; q.emplace(nx, ny); bear[nx][ny] = bear[x][y] + 1; prev[nx][ny] = {x, y}; } } vector <pii> path; int curx = ex, cury = ey; while (curx != -1 && cury != -1) { path.emb(curx, cury); int tx = curx, ty = cury; curx = prev[tx][ty].f; cury = prev[tx][ty].s; } reverse(path.begin(), path.end()); path.pop_back(); // for (auto [x, y] : path) cout << x << " " << y << "\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // cout << bee[i][j] << " "; } // cout << "\n"; } // cout << "--------------------\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { bear[i][j] = (bear[i][j] + k - 1) / k; // cout << bear[i][j] << " "; } // cout << "\n"; } int ans = inf; for (auto [x, y] : path) { ans = min(ans, bee[x][y] - bear[x][y]); } cout << (ans < 0 ? -1 : ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...