Submission #1196297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196297		ffeyyaae_	Mecho (IOI09_mecho)	C++20	56 / 100	113 ms	3912 KiB

mecho

#include <bits/stdc++.h>

#pragma GCC optimize("O3", "unroll-loops")

using namespace std;

const int N = 805;

int n, s;
char mp[N][N];
vector<vector<int>> dis( N, vector<int> (N, -1) );
queue<pair<int,int>> q;
pair<int,int> start, home;
int dy[] = {1, 0, -1, 0}, dx[] = {0, 1, 0, -1};

bool check( int ny, int nx )
{
    return (ny>=0 && ny<n && nx>=0 && nx<n && mp[ny][nx] != 'T' && mp[ny][nx] != 'D');
}

void bees()
{
    while( !q.empty() )
    {
        auto [y, x] = q.front();
        q.pop();
        for( int i=0;i<4;i++ )
        {
            int ny=y+dy[i], nx=x+dx[i];
            if( check(ny, nx) && dis[ny][nx] == -1 )
            {
                q.push( {ny, nx} );
                dis[ny][nx] = dis[y][x]+s;
            }
        }
    }
    // for( int i=0;i<n;i++ )
    // {
    //     for( int j=0;j<n;j++ ) cout << dis[i][j] << " ";
    //     cout << endl;
    // }
}

bool ok( int t )
{
    if( t*s >= dis[start.first][start.second] ) return false;
    //cout << "out\n";
    vector<vector<bool>> vis( N, vector<bool> (N, false) );
    queue<tuple<int,int,int>> qq;
    qq.push( {start.first, start.second, t*s} );
    vis[start.first][start.second] = true;
    while( !qq.empty() )
    {
        auto [y, x, path] = qq.front();
        qq.pop();
        //cout << "y " << y << " x " << x << " path " << path << endl;
        for( int i=0;i<4;i++ )
        {
            int ny = y+dy[i], nx=x+dx[i];
            if( check(ny, nx) && !vis[ny][nx] && path+1<dis[ny][nx] )
            {
                vis[ny][nx] = true;
                qq.push( {ny, nx, path+1} );
            }
        }
    }
    for( int i=0;i<4;i++ )
    {
        int yy = home.first-dy[i], xx = home.second-dx[i];
        if( vis[yy][xx] && check(yy, xx) ) return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    for( int i=0;i<n;i++ )
    {
        for( int j=0;j<n;j++ )
        {
            cin >> mp[i][j];
            if( mp[i][j] == 'H' )
            {
                q.push( {i, j} );
                dis[i][j] = 0;
            }
            else if( mp[i][j] == 'M' ) start = {i, j};
            else if( mp[i][j] == 'D' ) home ={i, j};
            //cout << dis[i][j] << " ";
        }
        //cout << endl;
    }
    bees();
    int l=0, r=n*n;
    while( l<r )
    {
        int mid = (l+r)/2;
        //cout << l << " " << r << " " << mid << endl;
        if( ok(mid) ) l = mid+1;
        else r = mid;
    }
    cout << l-1;
    return 0;
}

• Subtask 1: 56 / 100