# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
925953 | boris_mihov | Mecho (IOI09_mecho) | C++17 | 156 ms | 6464 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 800 + 10;
const int INF = 1e9;
int n, s;
char t[MAXN][MAXN];
int beeDist[MAXN][MAXN];
int myDist[MAXN][MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
std::queue <std::pair <int,int>> q;
bool inside(int row, int col)
{
return row >= 1 && row <= n && col >= 1 && col <= n;
}
bool check(int time)
{
time *= s;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= n ; ++j)
{
myDist[i][j] = INF;
if (t[i][j] == 'M')
{
if (beeDist[i][j] <= time)
{
return false;
}
myDist[i][j] = time;
q.push({i, j});
}
}
}
while (q.size())
{
auto [row, col] = q.front();
q.pop();
for (const auto &[dx, dy] : delta)
{
if (inside(row + dx, col + dy) && myDist[row][col] + 1 < beeDist[row + dx][col + dy] && t[row + dx][col + dy] != 'T' && myDist[row + dx][col + dy] == INF)
{
myDist[row + dx][col + dy] = myDist[row][col] + 1;
q.push({row + dx, col + dy});
}
}
}
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= n ; ++j)
{
if (t[i][j] == 'D')
{
return (myDist[i][j] != INF);
}
}
}
assert(false);
}
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= n ; ++j)
{
beeDist[i][j] = (t[i][j] == 'H' ? 0 : INF);
if (t[i][j] == 'H')
{
q.push({i, j});
beeDist[i][j] = 0;
}
}
}
while (q.size())
{
auto [row, col] = q.front();
q.pop();
for (const auto &[dx, dy] : delta)
{
if (inside(row + dx, col + dy) && t[row + dx][col + dy] != 'D' && t[row + dx][col + dy] != 'T' && beeDist[row + dx][col + dy] == INF)
{
beeDist[row + dx][col + dy] = beeDist[row][col] + s;
q.push({row + dx, col + dy});
}
}
}
int l = -1, r = n * n, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
std::cout << l << '\n';
}
void input()
{
std::cin >> n >> s;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> t[i] + 1;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |