Submission #1173465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173465		s101g	Mecho (IOI09_mecho)	C++20	0 / 100	59 ms	13788 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
vector<int> dr{-1, 1, 0, 0}, dc{0, 0, 1, -1};
int n, s, x, y, xx, yy;
vector<vector<char>> a;
vector<vector<bool>> vis;
vector<vector<vector<int>>> dis;
vector<vector<vector<int>>> d;
void dfs(int r, int c)
{
    if (r < 0 || r >= n || c < 0 || c >= n || vis[r][c] || a[r][c] == 'T' || dis[1][r][c] <= d[0][r][c])
        return;
    vis[r][c] = true;
    for (int i = 0; i < 4; i++)
    {
        int nr = r + dr[i];
        int nc = c + dc[i];
        dfs(nr, nc);
    }
}
bool check(int mid)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            d[0][i][j] = dis[0][i][j] + mid;
            vis[i][j] = false;
        }
    }
    dfs(x, y);
    return vis[xx][yy];
}
int main()
{
    cin >> n >> s;
    a = vector<vector<char>>(n, vector<char>(n));
    deque<pair<int, int>> node;
    vis = vector<vector<bool>>(n, vector<bool>(false));
    dis = vector<vector<vector<int>>>(2, vector<vector<int>>(n, vector<int>(n, 1e9)));
    d = vector<vector<vector<int>>>(2, vector<vector<int>>(n, vector<int>(n, 1e9)));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'H')
            {
                dis[1][i][j] = 0;
                node.push_back({i, j});
            }
            else if (a[i][j] == 'M')
            {
                dis[0][i][j] = 0;
                x = i, y = j;
            }
            else if (a[i][j] == 'D')
            {
                xx = i, yy = j;
            }
        }
    }
    while (!node.empty())
    {
        auto cur = node.front();
        int r = cur.first;
        int c = cur.second;
        node.pop_front();
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || a[nr][nc] == 'T' || a[nr][nc] == 'D')
                continue;
            if (dis[1][r][c] + 1 < dis[1][nr][nc])
            {
                dis[1][nr][nc] = dis[1][r][c] + 1;
                node.push_back({nr, nc});
            }
        }
    }
    node.push_back({x, y});
    while (!node.empty())
    {
        auto cur = node.front();
        int r = cur.first;
        int c = cur.second;
        node.pop_front();
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || a[nr][nc] == 'T')
                continue;
            if (dis[0][r][c] + 1 < dis[0][nr][nc])
            {
                dis[0][nr][nc] = dis[0][r][c] + 1;
                node.push_back({nr, nc});
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] != 'T')
            {
                dis[0][i][j] = dis[0][i][j] / s + (dis[0][i][j] % s == 0);
            }
        }
    }
    int l = -1, r = 2000;
    while (r > l + 1)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l;
    return 0;
}

• Subtask 1: 0 / 100