Submission #1212240

#TimeUsernameProblemLanguageResultExecution timeMemory
1212240plethMecho (IOI09_mecho)C++20
30 / 100
526 ms131072 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}; bool mecho(int wait) { queue<pair<int, int>> q; vector<vector<int>> mechoTime(n, vector<int>(n, 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] && forest[nextX][nextY] != 'T' && beeDist[nextX][nextY] > (mechoTime[x][y] + 1) / s + wait) { mechoTime[nextX][nextY] = mechoTime[x][y] + 1; q.push({nextX, nextY}); } } } return mechoTime[xEnd][yEnd] != INT_MAX; } 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)); 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' && beeDist[nextX][nextY] > beeDist[x][y] + 1) { beeDist[nextX][nextY] = beeDist[x][y] + 1; q.push({nextX, nextY}); } } } int l = 0, r = 1E9; 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...