| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 978530 | Bodisha | Mecho (IOI09_mecho) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX_N 801
using namespace std;
int n, s;char grid[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int beed[MAX_N][MAX_N];int steps[MAX_N][MAX_N]; bool check(int t) { pair<int, int> mecho_pos, home_pos; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { visited[i][j] = false; steps[i][j] = n * n; if(grid[i][j] == 'M') { mecho_pos = {i, j}; } if(grid[i][j] == 'D') { home_pos = {i, j}; } } } queue<pair<int, int>> q; visited[mecho_pos.first][mecho_pos.second] = true; steps[mecho_pos.first][mecho_pos.second] = 0; q.push(mecho_pos); while(!q.empty()) { pair<int, int> curr = q.front(); q.pop(); if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M' || grid[curr.first + 1][curr.second] == 'D')) { visited[curr.first + 1][curr.second] = true; steps[curr.first + 1][curr.second] = steps[curr.first][curr.second] + 1; q.push({curr.first + 1, curr.second}); } if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M' || grid[curr.first - 1][curr.second] == 'D')) { visited[curr.first - 1][curr.second] = true; steps[curr.first - 1][curr.second] = steps[curr.first][curr.second] + 1; q.push({curr.first - 1, curr.second}); } if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M' || grid[curr.first][curr.second + 1] == 'D')) { visited[curr.first][curr.second + 1] = true; steps[curr.first][curr.second + 1] = steps[curr.first][curr.second] + 1; q.push({curr.first, curr.second + 1}); } if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M' || grid[curr.first][curr.second - 1] == 'D')) { visited[curr.first][curr.second - 1] = true; steps[curr.first][curr.second - 1] = steps[curr.first][curr.second] + 1; q.push({curr.first, curr.second - 1}); } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { visited[i][j] = false; } } if(t + 1 > beed[mecho_pos.first][mecho_pos.second]) { return false; } queue<pair<pair<int, int>, int>> newq; visited[mecho_pos.first][mecho_pos.second] = true; newq.push({mecho_pos, 0}); while(!newq.empty()) { pair<pair<int, int>, int> curr = newq.front(); newq.pop(); int tmp = t + 1 + (curr.second + 1) / s; if(curr.first.first + 1 < n && tmp <= beed[curr.first.first + 1][curr.first.second] && !visited[curr.first.first + 1][curr.first.second] && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'M' || grid[curr.first.first + 1][curr.first.second] == 'D')) { visited[curr.first.first + 1][curr.first.second] = true; newq.push({{curr.first.first + 1, curr.first.second}, curr.second + 1}); } if(curr.first.first - 1 >= 0 && tmp <= beed[curr.first.first - 1][curr.first.second] && !visited[curr.first.first - 1][curr.second] && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'M' || grid[curr.first.first - 1][curr.first.second] == 'D')) { visited[curr.first.first - 1][curr.first.second] = true; newq.push({{curr.first.first - 1, curr.first.second}, curr.second + 1}); } if(curr.first.second + 1 < n && tmp <= beed[curr.first.first][curr.first.second + 1] && !visited[curr.first.first][curr.first.second + 1] && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'M' || grid[curr.first.first][curr.first.second + 1] == 'D')) { visited[curr.first.first][curr.first.second + 1] = true; newq.push({{curr.first.first, curr.first.second + 1}, curr.second + 1}); } if(curr.first.second - 1 >= 0 && tmp <= beed[curr.first.first][curr.first.second - 1] && !visited[curr.first.first][curr.first.second - 1] && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'M' || grid[curr.first.first][curr.first.second - 1] == 'D')) { visited[curr.first.first][curr.first.second - 1] = true; newq.push({{curr.first.first, curr.first.second - 1}, curr.second + 1}); } } return visited[home_pos.first + 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first][home_pos.second + 1] || visited[home_pos.first][home_pos.second - 1];} int main() { vector<pair<int, int>> hives; cin >> n >> s; for(int i = 0; i < n; i++) { string tmp; cin >> tmp; for(int j = 0; j < n; j++) { grid[i][j] = tmp[j]; if(grid[i][j] == 'H') { hives.push_back({i, j}); } } } queue<pair<int, int>> q; for(auto iter : hives) { visited[iter.first][iter.second] = true; beed[iter.first][iter.second] = 0; q.push(iter); } while(!q.empty()) { pair<int, int> curr = q.front(); q.pop(); if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) { visited[curr.first + 1][curr.second] = true; beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1; q.push({curr.first + 1, curr.second}); } if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) { visited[curr.first - 1][curr.second] = true; beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1; q.push({curr.first - 1, curr.second}); } if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) { visited[curr.first][curr.second + 1] = true; beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1; q.push({curr.first, curr.second + 1}); } if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) { visited[curr.first][curr.second - 1] = true; beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1; q.push({curr.first, curr.second - 1}); } } int l = 0, r = n * n; int ans = -1; // true true true ... (true) false false while(l <= r) { int mid = l + (r - l) / 2; if(check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans; return 0;}#define MAX_N 801 using namespace std; int n, s;char grid[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int beed[MAX_N][MAX_N];int steps[MAX_N][MAX_N]; bool check(int t) { pair<int, int> mecho_pos, home_pos; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { visited[i][j] = false; steps[i][j] = n * n; if(grid[i][j] == 'M') { mecho_pos = {i, j}; } if(grid[i][j] == 'D') { home_pos = {i, j}; } } } queue<pair<int, int>> q; visited[mecho_pos.first][mecho_pos.second] = true; steps[mecho_pos.first][mecho_pos.second] = 0; q.push(mecho_pos); while(!q.empty()) { pair<int, int> curr = q.front(); q.pop(); if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M' || grid[curr.first + 1][curr.second] == 'D')) { visited[curr.first + 1][curr.second] = true; steps[curr.first + 1][curr.second] = steps[curr.first][curr.second] + 1; q.push({curr.first + 1, curr.second}); } if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M' || grid[curr.first - 1][curr.second] == 'D')) { visited[curr.first - 1][curr.second] = true; steps[curr.first - 1][curr.second] = steps[curr.first][curr.second] + 1; q.push({curr.first - 1, curr.second}); } if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M' || grid[curr.first][curr.second + 1] == 'D')) { visited[curr.first][curr.second + 1] = true; steps[curr.first][curr.second + 1] = steps[curr.first][curr.second] + 1; q.push({curr.first, curr.second + 1}); } if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M' || grid[curr.first][curr.second - 1] == 'D')) { visited[curr.first][curr.second - 1] = true; steps[curr.first][curr.second - 1] = steps[curr.first][curr.second] + 1; q.push({curr.first, curr.second - 1}); } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { visited[i][j] = false; } } if(t + 1 > beed[mecho_pos.first][mecho_pos.second]) { return false; } queue<pair<pair<int, int>, int>> newq; visited[mecho_pos.first][mecho_pos.second] = true; newq.push({mecho_pos, 0}); while(!newq.empty()) { pair<pair<int, int>, int> curr = newq.front(); newq.pop(); int tmp = t + 1 + ((curr.second + 1) / (s + 1)); if(curr.first.first + 1 < n && tmp <= beed[curr.first.first + 1][curr.first.second] && !visited[curr.first.first + 1][curr.first.second] && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'M' || grid[curr.first.first + 1][curr.first.second] == 'D')) { visited[curr.first.first + 1][curr.first.second] = true; newq.push({{curr.first.first + 1, curr.first.second}, curr.second + 1}); } if(curr.first.first - 1 >= 0 && tmp <= beed[curr.first.first - 1][curr.first.second] && !visited[curr.first.first - 1][curr.second] && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'M' || grid[curr.first.first - 1][curr.first.second] == 'D')) { visited[curr.first.first - 1][curr.first.second] = true; newq.push({{curr.first.first - 1, curr.first.second}, curr.second + 1}); } if(curr.first.second + 1 < n && tmp <= beed[curr.first.first][curr.first.second + 1] && !visited[curr.first.first][curr.first.second + 1] && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'M' || grid[curr.first.first][curr.first.second + 1] == 'D')) { visited[curr.first.first][curr.first.second + 1] = true; newq.push({{curr.first.first, curr.first.second + 1}, curr.second + 1}); } if(curr.first.second - 1 >= 0 && tmp <= beed[curr.first.first][curr.first.second - 1] && !visited[curr.first.first][curr.first.second - 1] && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'M' || grid[curr.first.first][curr.first.second - 1] == 'D')) { visited[curr.first.first][curr.first.second - 1] = true; newq.push({{curr.first.first, curr.first.second - 1}, curr.second + 1}); } } return visited[home_pos.first + 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first][home_pos.second + 1] || visited[home_pos.first][home_pos.second - 1];} int main() { vector<pair<int, int>> hives; cin >> n >> s; for(int i = 0; i < n; i++) { string tmp; cin >> tmp; for(int j = 0; j < n; j++) { grid[i][j] = tmp[j]; if(grid[i][j] == 'H') { hives.push_back({i, j}); } } } queue<pair<int, int>> q; for(auto iter : hives) { visited[iter.first][iter.second] = true; beed[iter.first][iter.second] = 0; q.push(iter); } while(!q.empty()) { pair<int, int> curr = q.front(); q.pop(); if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) { visited[curr.first + 1][curr.second] = true; beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1; q.push({curr.first + 1, curr.second}); } if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) { visited[curr.first - 1][curr.second] = true; beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1; q.push({curr.first - 1, curr.second}); } if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) { visited[curr.first][curr.second + 1] = true; beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1; q.push({curr.first, curr.second + 1}); } if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) { visited[curr.first][curr.second - 1] = true; beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1; q.push({curr.first, curr.second - 1}); } } int l = 0, r = n * n; int ans = -1;
// true true true ... (true) false false while(l <= r) { int mid = l + (r - l) / 2; if(check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans; return 0;}#define MAX_N 801 using namespace std; int n, s;char grid[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int beed[MAX_N][MAX_N];int steps[MAX_N][MAX_N]; bool check(int t) { pair<int, int> mecho_pos, home_pos; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { visited[i][j] = false; steps[i][j] = n * n; if(grid[i][j] == 'M') { mecho_pos = {i, j}; } if(grid[i][j] == 'D') { home_pos = {i, j}; } } } queue<pair<int, int>> q; visited[mecho_pos.first][mecho_pos.second] = true; steps[mecho_pos.first][mecho_pos.second] = 0; q.push(mecho_pos); while(!q.empty()) { pair<int, int> curr = q.front(); q.pop(); if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M' || grid[curr.first + 1][curr.second] == 'D')) { visited[curr.first + 1][curr.second] = true; steps[curr.first + 1][curr.second] = steps[curr.first][curr.second] + 1; q.push({curr.first + 1, curr.second}); } if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M' || grid[curr.first - 1][curr.second] == 'D')) { visited[curr.first - 1][curr.second] = true; steps[curr.first - 1][curr.second] = steps[curr.first][curr.second] + 1; q.push({curr.first - 1, curr.second}); } if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M' || grid[curr.first][curr.second + 1] == 'D')) { visited[curr.first][curr.second + 1] = true; steps[curr.first][curr.second + 1] = steps[curr.first][curr.second] + 1; q.push({curr.first, curr.second + 1}); } if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M' || grid[curr.first][curr.second - 1] == 'D')) { visited[curr.first][curr.second - 1] = true; steps[curr.first][curr.second - 1] = steps[curr.first][curr.second] + 1; q.push({curr.first, curr.second - 1}); } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { visited[i][j] = false; } } if(t + 1 > beed[mecho_pos.first][mecho_pos.second]) { return false; } queue<pair<pair<int, int>, int>> newq; visited[mecho_pos.first][mecho_pos.second] = true; newq.push({mecho_pos, 0}); while(!newq.empty()) { pair<pair<int, int>, int> curr = newq.front(); newq.pop(); int tmp = t + 1 + ((curr.second + 1) / (s + 1)); if(curr.first.first + 1 < n && tmp <= beed[curr.first.first + 1][curr.first.second] && !visited[curr.first.first + 1][curr.first.second] && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'M' || grid[curr.first.first + 1][curr.first.second] == 'D')) { visited[curr.first.first + 1][curr.first.second] = true; newq.push({{curr.first.first + 1, curr.first.second}, curr.second + 1}); } if(curr.first.first - 1 >= 0 && tmp <= beed[curr.first.first - 1][curr.first.second] && !visited[curr.first.first - 1][curr.second] && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'M' || grid[curr.first.first - 1][curr.first.second] == 'D')) { visited[curr.first.first - 1][curr.first.second] = true; newq.push({{curr.first.first - 1, curr.first.second}, curr.second + 1}); } if(curr.first.second + 1 < n && tmp <= beed[curr.first.first][curr.first.second + 1] && !visited[curr.first.first][curr.first.second + 1] && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'M' || grid[curr.first.first][curr.first.second + 1] == 'D')) { visited[curr.first.first][curr.first.second + 1] = true; newq.push({{curr.first.first, curr.first.second + 1}, curr.second + 1}); } if(curr.first.second - 1 >= 0 && tmp <= beed[curr.first.first][curr.first.second - 1] && !visited[curr.first.first][curr.first.second - 1] && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'M' || grid[curr.first.first][curr.first.second - 1] == 'D')) { visited[curr.first.first][curr.first.second - 1] = true; newq.push({{curr.first.first, curr.first.second - 1}, curr.second + 1}); } } return visited[home_pos.first + 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first][home_pos.second + 1] || visited[home_pos.first][home_pos.second - 1];} int main() { vector<pair<int, int>> hives; cin >> n >> s; for(int i = 0; i < n; i++) { string tmp; cin >> tmp; for(int j = 0; j < n; j++) { grid[i][j] = tmp[j]; if(grid[i][j] == 'H') { hives.push_back({i, j}); } } } queue<pair<int, int>> q; for(auto iter : hives) { visited[iter.first][iter.second] = true; beed[iter.first][iter.second] = 0; q.push(iter); } while(!q.empty()) { pair<int, int> curr = q.front(); q.pop(); if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) { visited[curr.first + 1][curr.second] = true; beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1; q.push({curr.first + 1, curr.second}); } if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) { visited[curr.first - 1][curr.second] = true; beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1; q.push({curr.first - 1, curr.second}); } if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) { visited[curr.first][curr.second + 1] = true; beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1; q.push({curr.first, curr.second + 1}); } if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) { visited[curr.first][curr.second - 1] = true; beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1; q.push({curr.first, curr.second - 1}); } } int l = 0, r = n * n; int ans = -1; // true true true ... (true) false false while(l <= r) { int mid = l + (r - l) / 2; if(check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans; return 0;}