Submission #956844

#	Time	Username	Problem	Language	Result	Execution time	Memory
956844		wood	Mecho (IOI09_mecho)	C++17	84 / 100	139 ms	6480 KiB

mecho

#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007

int dfx[4] = {1,-1,0,0}; int dfy[4] = {0,0,1,-1};

int main()
{
    fast_cin();
    #ifndef ONLINE_JUDGE
        #ifdef _WIN32
            freopen("input.in", "r", stdin);
            freopen("input.out", "w", stdout);
        #endif
    #endif
    int n,s; cin>>n>>s;
    char arr[n][n];
    int bees[n][n];
    fill(bees[0],bees[0]+n*n,INT_MAX);
    queue<p32> hq;
    p32 start;
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            cin>>arr[i][j];
            if(arr[i][j]=='H'){
               bees[i][j] = 1; 
                hq.emplace(i,j);
            }
            if(arr[i][j]=='M') start = p32(i,j);
        }
    }
    while(!hq.empty()){
        for (size_t i = 0; i < 4; i++)
        {
            int x = hq.front().fi+dfx[i];
            int y = hq.front().se+dfy[i];
            if(x>=0&&x<n&&y>=0&&y<n&&bees[x][y]==INT_MAX&&arr[x][y]!='T'&&arr[x][y]!='D'){
                bees[x][y] = bees[hq.front().fi][hq.front().se] + 1;
                hq.emplace(x,y);
            }
        }
        hq.pop();
    }
    int l = -1; 
    int r = 1e9;
    while(r-l>1){
        int mid = (l+r)/2;
        queue<p32> q;
        q.push(start);
        int depth[n][n];
        memset(depth,0,sizeof depth);
        depth[start.fi][start.se] = 1;
        while(!q.empty()){
            for (size_t i = 0; i < 4; i++)
            {
                int x = q.front().fi+dfx[i];
                int y = q.front().se+dfy[i];
                int d = depth[q.front().fi][q.front().se];
                if(x>=0&&x<n&&y>=0&&y<n&&!depth[x][y]&&arr[x][y]!='T'&&(d+s)/s+mid<bees[x][y]){
                    if(arr[x][y]=='D'){
                        l = mid;
                        goto next;
                    }
                    depth[x][y] = d+1;
                    q.emplace(x,y);
                }
            }
            q.pop();
        }
        r = mid;
        next: 
        continue;
    }
    cout<<l<<'\n';
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:31:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
mecho.cpp:33:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         for (size_t j = 0; j < n; j++)
      |                            ~~^~~

• Subtask 1: 84 / 100