Submission #982895

#	Time	Username	Problem	Language	Result	Execution time	Memory
982895		doducanh	Mecho (IOI09_mecho)	C++17	100 / 100	174 ms	6544 KiB

mecho

#include <bits/stdc++.h>

using namespace std;
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
string fields[805];
int beetime[805][805];
int mechotime[805][805];
int n,s;
bool check(int x,int y)
{
    return (x>=0&&x<n&&y>=0&&y<n&&(fields[x][y]=='G'||fields[x][y]=='M'));
}
bool is_acc(int x,int y)
{
    return ((x/s)<y);
}
int main()
{
    cin>>n>>s;
    for(int i=0;i<n;i++)cin>>fields[i];
    int mechoposx,mechoposy;
    int mechohomex,mechohomey;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            beetime[i][j]=-1;
        }
    }
    queue<pair<int,int>>q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(fields[i][j]=='M'){
                mechoposx=i;
                mechoposy=j;
            }
            if(fields[i][j]=='D'){
                mechohomex=i;
                mechohomey=j;
            }
            if(fields[i][j]=='H'){
                beetime[i][j]=0;
                q.push({i,j});
            }
        }
    }
    while(q.size()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(check(nx,ny)&&beetime[nx][ny]==-1){
                beetime[nx][ny]=beetime[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    int l=0,r=n*n;
    int res=-1;
    while(l<=r){
        int eating_time=(l+r)/2;
        q.push({mechoposx,mechoposy});
        if(beetime[mechoposx][mechoposy]<=eating_time)q.pop();
        bool acc=false;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                mechotime[i][j]=-1;
            }
        }
        mechotime[mechoposx][mechoposy]=0;
        while(q.size()){
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(check(nx,ny)&&mechotime[nx][ny]==-1&&is_acc(mechotime[x][y]+1,beetime[nx][ny]-eating_time)) {
                    mechotime[nx][ny]=mechotime[x][y]+1;
                    q.push({nx,ny});
                }
            }
        }
        for(int i=0;i<4;i++){
            int nx=mechohomex+dx[i];
            int ny=mechohomey+dy[i];
            if(check(nx,ny)&&mechotime[nx][ny]!=-1&&is_acc(mechotime[nx][ny],beetime[nx][ny]-eating_time)){
                acc=true;
                break;
            }
        }
        if(acc){
            res=eating_time;
            l=eating_time+1;
        }
        else r=eating_time-1;
    }
    cout<<res;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:71:40: warning: 'mechoposy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |         mechotime[mechoposx][mechoposy]=0;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
mecho.cpp:71:40: warning: 'mechoposx' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:88:17: warning: 'mechohomey' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |             int ny=mechohomey+dy[i];
      |                 ^~
mecho.cpp:87:17: warning: 'mechohomex' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |             int nx=mechohomex+dx[i];
      |                 ^~

• Subtask 1: 100 / 100