제출 #511162

#제출 시각아이디문제언어결과실행 시간메모리
511162600MihneaMecho (IOI09_mecho)C++17
30 / 100
157 ms16660 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000 + 7; const int INF = (int) 1e9 + 7; int dr[] = {-1, 0, 1, 0}; int dc[] = {0, 1, 0, -1}; int n; int speed; int r1, c1; int r2, c2; int a[N][N]; int dist_m[N][N]; int dist_b[N][N]; vector<pair<int, int>> ord; void compute(int dist[N][N], vector<pair<int, int>> init) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = INF; } } queue<pair<int, int>> q; for (auto &it : init) { dist[it.first][it.second] = 0; q.push(it); } while (!q.empty()) { auto it = q.front(); int r = it.first; int c = it.second; ord.push_back(it); q.pop(); for (int k = 0; k < 4; k++) { int rn = r + dr[k]; int cn = c + dc[k]; if (a[rn][cn] && dist[rn][cn] == INF) { dist[rn][cn] = 1 + dist[r][c]; q.push({rn, cn}); } } } } int dist[N][N]; bool ok[N][N]; signed main() { ios::sync_with_stdio(0); cin.tie(0); /// freopen ("input", "r", stdin); cin >> n >> speed; vector<pair<int, int>> bees; for (int i = 1; i <= n; i++) { string s; cin >> s; for (int j = 1; j <= n; j++) { char ch = s[j - 1]; if (ch == 'T') { a[i][j] = 0; continue; } if (ch == 'G') { a[i][j] = 1; continue; } if (ch == 'M') { r1 = i; c1 = j; a[i][j] = 1; continue; } if (ch == 'D') { r2 = i; c2 = j; a[i][j] = 1; continue; } if (ch == 'H') { bees.push_back({i, j}); continue; } } } vector<pair<int, int>> m; m.push_back({r1, c1}); compute(dist_b, bees); ord.clear(); compute(dist_m, m); int low = 0, high = dist_b[r1][c1], sol = -1; while (low <= high) { int stay = (low + high) / 2; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { ok[i][j] = 0; } } ok[r1][c1] = 1; for (auto &it : ord) { if (ok[it.first][it.second]) { int r = it.first, c = it.second; for (int k = 0; k < 4; k++) { int rn = r + dr[k]; int cn = c + dc[k]; ok[rn][cn] |= (stay + (dist_m[rn][cn] + speed - 1) / speed <= dist_b[rn][cn]); } } } if (ok[r2][c2]) { sol = stay; low = stay + 1; } else { high = stay - 1; } } cout << sol << "\n"; return 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int val = dist_m[i][j]; if (val == INF) { cout << "- "; } else { cout << val << " "; } } cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...