Submission #925950

#	Time	Username	Problem	Language	Result	Execution time	Memory
925950		boris_mihov	Mecho (IOI09_mecho)	C++17	53 / 100	143 ms	6396 KiB

mecho

#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 = 3 * 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;
}

Compilation message (stderr)

mecho.cpp: In function 'void input()':
mecho.cpp:120:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |         std::cin >> t[i] + 1;
      |                     ~~~~~^~~

• Subtask 1: 53 / 100