Submission #135951

#	Time	Username	Problem	Language	Result	Execution time	Memory
135951		Dilshod_Imomov	Mecho (IOI09_mecho)	C++17	100 / 100	266 ms	6392 KiB

mecho

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pb push_back
# define pf push_front
# define For(i, a, b) for( int i = a; i < b; i++ )
# define in insert
# define all(a) a.begin(),a.end()
# define pi pair < int, int >
# define DEBUG
# define readfile(file) freopen ( (file + ".in").c_str(), "r", stdin)
# define writefile(file) freopen ( (file + ".out").c_str(), "w", stdout)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
# define LARGE 1000
# define SET(file) readfile(file);writefile(file);

using namespace std;

int ax[4] = { 1, -1, 0, 0 };
int ay[4] = { 0, 0, 1, -1 };

char mainMap[LARGE][LARGE];
bool visited[LARGE][LARGE];
int beeDistance[LARGE][LARGE];

int n, s;
int dx, dy;
int mx, my;

bool valid( int i, int j )
{
    if ( i >= 0 && i < n && j >= 0 && j < n && mainMap[i][j] != 'T' )
        return 1;
    return 0;
}

bool test( int delay )
{
    if ( delay * s >= beeDistance[mx][my] )
        return false;

    memset(visited, 0, sizeof(visited));
    queue < pair < int, pi > > q;
    q.push({delay * s, {mx, my}});
    visited[mx][my] = true;

    while (!q.empty())
    {
        int distance = q.front().fi;
        int x = q.front().se.fi;
        int y = q.front().se.se;

        q.pop();

        if ( mainMap[x][y] == 'D' )
            return true;

        For ( i, 0, 4)
        {
            int nx = x + ax[i];
            int ny = y + ay[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= n || mainMap[nx][ny] == 'T' || (distance + 1) >= beeDistance[nx][ny] || visited[nx][ny])
                continue;

            q.push({distance + 1, {nx, ny}});
            visited[nx][ny] = true;
        }
    }
    return false;
}

int main()
{
    /// Author: _Dilshod_
    speed;
    cin >> n >> s;

    queue < pi > bq;
    memset(beeDistance, -1, sizeof(beeDistance));

    For ( i, 0, n )
    {
        For ( j, 0, n )
        {
            cin >> mainMap[i][j];

            if ( mainMap[i][j] == 'D' )
            {
                dx = i;
                dy = j;
            } else if ( mainMap[i][j] == 'H' )
            {
                bq.push({i, j});
                beeDistance[i][j] = 0;
            } else if ( mainMap[i][j] == 'M' )
            {
                mx = i;
                my = j;
                mainMap[i][j] = 'G';
            }
        }
    }
    while( !bq.empty() )
    {
        int x = bq.front().fi;
        int y = bq.front().se;

        bq.pop();

        For ( i, 0, 4 )
        {
            int nx = x + ax[i];
            int ny = y + ay[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || mainMap[nx][ny] != 'G' || beeDistance[nx][ny] != -1)
                continue;
            beeDistance[nx][ny] = beeDistance[x][y] + s;
            bq.push({nx, ny});
        }
    }
    beeDistance[dx][dy] = n * n * s;
    int l = -1, r = 2 * n * n, m;
    while (r - l > 1 )
    {
        m = (l + r) >> 1;
        if ( test(m) ) l = m;
        else r = m;
    }
    cout << l;
}

• Subtask 1: 100 / 100