Submission #705899

#	Time	Username	Problem	Language	Result	Execution time	Memory
705899		ToroTN	Mecho (IOI09_mecho)	C++14	84 / 100	208 ms	9416 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,stx,sty,edx,edy,bee[805][805],st,md,ed,d[805][805],bear[805][805];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1},u,v,x,y;
char s[805][805];
queue<pair<int,int> > q;
void debug(int kk)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(bee[i][j]==1e9)
            {
                printf("-1 ");
                continue;
            }
            printf("%d ",bee[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(bear[i][j]==1e9)
            {
                printf("-1 ");
                continue;
            }
            printf("%d ",bear[i][j]/m+kk);
        }
        printf("\n");
    }
    printf("\n");
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)bee[i][j]=1e9,bear[i][j]=1e9;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(s[i][j]=='M')
            {
                stx=i,sty=j;
            }else if(s[i][j]=='D')
            {   
                edx=i,edy=j;
            }else if(s[i][j]=='H')
            {
                q.push({i,j});
                bee[i][j]=0;
            }
        }
    }
    while(!q.empty())
    {
        u=q.front().X,v=q.front().Y;
        q.pop();
        for(int i=0;i<4;i++)
        {
            x=u+dx[i],y=v+dy[i];
            if(x>=1&&x<=n&&y>=1&&y<=n)
            {
                if((s[x][y]=='G'||s[x][y]=='M')&&bee[x][y]==1e9)
                {
                    bee[x][y]=bee[u][v]+1;
                    q.push({x,y});
                }
            }
        }
    }
    /*
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(bee[i][j]==1e9)
            {
                printf("-1 ");
                continue;
            }
            printf("%d ",bee[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(bear[i][j]==1e9)
            {
                printf("-1 ");
                continue;
            }
            printf("%d ",bear[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    */
    st=0;
    ed=1e9;
    while(ed>=st)
    {
        md=(st+ed)/2;
        //printf("%d %d %d\n",st,md,ed);
        memset(d,-1,sizeof d);
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)bear[i][j]=1e9;
        d[stx][sty]=0;
        bear[stx][sty]=0;
        q.push({stx,sty});
        while(!q.empty())
        {
            u=q.front().X,v=q.front().Y;
            q.pop();
            for(int i=0;i<4;i++)
            {
                x=u+dx[i],y=v+dy[i];
                if(x>=1&&x<=n&&y>=1&&y<=n)
                {
                    if((s[x][y]=='G'||s[x][y]=='M'||s[x][y]=='D')&&d[x][y]==-1)
                    {
                        if((bear[u][v]+1)/m+md<bee[x][y])
                        {
                            d[x][y]=0;
                            bear[x][y]=bear[u][v]+1;
                            q.push({x,y});
                        }
                    }
                }
            }
        }
        //debug(md);
        if(d[edx][edy]==0)
        {
            st=md+1;
        }else
        {
            ed=md-1;
        }
    }
    //printf("%d %d %d\n",st,md,ed);
    printf("%d\n",ed);
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
mecho.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%s",s[i]+1);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 84 / 100