# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
839394 | ArashJafariyan | Mecho (IOI09_mecho) | C++17 | 210 ms | 6540 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>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define pb push_back
#define size(a) (int) a.size()
#define all(a) a.begin(), a.end()
const int maxn = 800 + 4, inf = 1e8;
int n, s, mx, my, dx, dy, d[maxn][maxn], save[maxn][maxn];
bitset<maxn> vis[maxn], savevis[maxn];
string a[maxn];
queue<array<int, 2>> q;
void rest() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
vis[i][j] = 0;
d[i][j] = inf;
}
}
return;
}
bool check0(int x, int y) {
bool ret = ((0 <= x) && (x < n));
ret &= ((0 <= y) && (y < n));
if (ret) {
ret &= (!vis[x][y]);
ret &= ((a[x][y] == 'G') || (a[x][y] == 'M'));
}
return ret;
}
void upd0(int x, int y) {
int dis = d[x][y] + 1;
if (check0(x - 1, y)) {
vis[x - 1][y] = 1;
d[x - 1][y] = dis;
q.push({x - 1, y});
}
if (check0(x + 1, y)) {
vis[x + 1][y] = 1;
d[x + 1][y] = dis;
q.push({x + 1, y});
}
if (check0(x, y - 1)) {
vis[x][y - 1] = 1;
d[x][y - 1] = dis;
q.push({x, y - 1});
}
if (check0(x, y + 1)) {
vis[x][y + 1] = 1;
d[x][y + 1] = dis;
q.push({x, y + 1});
}
}
bool check1(int x, int y, int dis, int k) {
bool ret = ((0 <= x) && (x < n));
ret &= ((0 <= y) && (y < n));
if (ret) {
ret &= (!vis[x][y]);
ret &= ((a[x][y] == 'G') || (a[x][y] == 'D'));
ret &= ((((dis + s - 1) / s) <= (save[x][y] - k)) || !savevis[x][y]);
}
return ret;
}
void upd1(int x, int y, int k) {
int dis = d[x][y] + 1;
if (check1(x - 1, y, dis, k)) {
vis[x - 1][y] = 1;
d[x - 1][y] = dis;
q.push({x - 1, y});
}
if (check1(x + 1, y, dis, k)) {
vis[x + 1][y] = 1;
d[x + 1][y] = dis;
q.push({x + 1, y});
}
if (check1(x, y - 1, dis, k)) {
vis[x][y - 1] = 1;
d[x][y - 1] = dis;
q.push({x, y - 1});
}
if (check1(x, y + 1, dis, k)) {
vis[x][y + 1] = 1;
d[x][y + 1] = dis;
q.push({x, y + 1});
}
}
bool bfs(int k) {
rest();
d[mx][my] = 0;
vis[mx][my] = 1;
q.push({mx, my});
while (!q.empty()) {
array<int, 2> v = q.front();
q.pop();
if (d[v[0]][v[1]] % s == 0 && d[v[0]][v[1]] / s == save[v[0]][v[1]] - k) {
continue;
}
upd1(v[0], v[1], k);
}
return (d[dx][dy] != inf);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> s;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'H') {
q.push({i, j});
vis[i][j] = 1;
}
}
}
while (!q.empty()) {
array<int, 2> v = q.front();
q.pop();
upd0(v[0], v[1]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'M') {
mx = i;
my = j;
}
if (a[i][j] == 'D') {
dx = i;
dy = j;
}
save[i][j] = d[i][j];
savevis[i][j] = vis[i][j];
}
}
int l, r;
l = -1;
r = save[mx][my];
while (r - l > 1) {
int m = (l + r) >> 1;
if (bfs(m)) {
l = m;
}
else {
r = m;
}
}
cout << l << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |