제출 #1175702

#제출 시각아이디문제언어결과실행 시간메모리
1175702jadai007Mecho (IOI09_mecho)C++17
84 / 100
177 ms16360 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 = 1e6; const int mod = 998244353; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; bool can(int k, int n, int sx, int sy, int ex, int ey, vector <vector <int>> &bee, vector <vector <char>> &a, int mid) { //if (bee[sx][sy] <= mid) return false; queue <pii> q; q.emplace(sx, sy); vector <vector <int>> bear(n, vector <int> (n, inf)); vector <vector <bool>> home(n, vector <bool> (n)); for (int i = 0; i < 4; i++) { int eex = ex + dx[i], eey = ey + dy[i]; if (eex < 0 || eex >= n || eey < 0 || eey >= n) continue; home[eex][eey] = true; } bear[sx][sy] = 0; 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]; int dist = (bear[x][y]+1) / k; if (nx < 0 || nx >= n || ny < 0 || ny >= n || bear[nx][ny] != inf || dist + mid >= bee[nx][ny] || a[nx][ny] == 'T') continue; if (home[nx][ny]) return true; bear[nx][ny] = bear[x][y]+1; q.emplace(nx, ny); } } return false; } int32_t main(){ iShowSpeed; int n, k; cin >> n >> k; vector <vector <char>> a(n, vector <char> (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)); 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 || a[nx][ny] == 'T') continue; q.emplace(nx, ny); bee[nx][ny] = bee[x][y] + 1; } } int sx, sy, ex, ey; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 'M') sx = i, sy = j; if (a[i][j] == 'D') ex = i, ey = j; } } int ans = -1; int l = 0, r = n * n; while (l <= r) { int mid = (l + r) / 2; if (can(k, n, sx, sy, ex, ey, bee, a, mid)) { l = mid + 1; ans = max(ans, mid); } else r = mid - 1; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...