Submission #1212252

#TimeUsernameProblemLanguageResultExecution timeMemory
1212252plethMecho (IOI09_mecho)C++20
100 / 100
152 ms6472 KiB
#include <climits> #include <iostream> #include <queue> #include <vector> using namespace std; int n, s; vector<string> forest; vector<vector<int>> beeDist; int xStart, yStart, xEnd, yEnd; vector<int> dirx = {1, 0, -1, 0}, diry = {0, 1, 0, -1}; vector<vector<int>> mechoTime; bool mecho(int wait) { if(wait>=beeDist[xStart][yStart]) { return false; } queue<pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { mechoTime[i][j] = INT_MAX; } } mechoTime[xStart][yStart] = 0; q.push({xStart, yStart}); while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nextX = x + dirx[i], nextY = y + diry[i]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && mechoTime[nextX][nextY] > mechoTime[x][y] + 1 && forest[nextX][nextY] != 'T' && forest[nextX][nextY]!='D' && beeDist[nextX][nextY] * s > (mechoTime[x][y] + 1) + wait * s) { mechoTime[nextX][nextY] = mechoTime[x][y] + 1; q.push({nextX, nextY}); } } } for (int i = 0; i < 4; i++) { int nextX = xEnd + dirx[i], nextY = yEnd + diry[i]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && mechoTime[nextX][nextY] != INT_MAX) { return true; } } return false; } int main() { cin >> n >> s; forest.resize(n); for (int i = 0; i < n; i++) { cin >> forest[i]; } queue<pair<int, int>> q; beeDist.resize(n, vector<int>(n, INT_MAX)); mechoTime.resize(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (forest[i][j] == 'H') { q.push({i, j}); beeDist[i][j] = 0; } else if (forest[i][j] == 'M') { xStart = i; yStart = j; } else if (forest[i][j] == 'D') { xEnd = i; yEnd = j; } } } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nextX = x + dirx[i], nextY = y + diry[i]; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && forest[nextX][nextY] != 'T' && forest[nextX][nextY] != 'D' && beeDist[nextX][nextY] > beeDist[x][y] + 1) { beeDist[nextX][nextY] = beeDist[x][y] + 1; q.push({nextX, nextY}); } } } int l = 0, r = n * n; while (l <= r) { int m = (r - l) / 2 + l; if (mecho(m)) { l = m + 1; } else { r = m - 1; } } cout << r << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...