Submission #1175630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175630		prideliqueee	Mecho (IOI09_mecho)	C++20	38 / 100	144 ms	6544 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define fff first
#define sss second
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};
struct st
{
    int i,j,w;
};
struct e
{
    int i,j,sec,step;
};
int main()
{
    int n,ss;
    cin>>n>>ss;
    string s[n];
    int mx,my,dx,dy;
    int t[n][n];
    memset(t,-1,sizeof t);
    queue<st> q;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        for(int j=0;j<n;j++)
        {
            if(s[i][j]=='M')
            mx=i,my=j;
            if(s[i][j]=='D')
            dx=i,dy=j;
            if(s[i][j]=='H')
            {
                t[i][j]=0;
                q.push({i,j,0});
            }
        }
    }
    while(!q.empty())
    {
        auto p=q.front();
        q.pop();
        int i=p.i,j=p.j,w=p.w;
        if(t[i][j]<w)
        continue;
        for(int k=0;k<4;k++)
        {
            int ii=i+di[k],jj=j+dj[k];
            if(ii<0||ii>=n||jj<0||jj>=n)
            continue;
            if(t[ii][jj]==-1&&s[ii][jj]=='G')
            {
                t[ii][jj]=w+1;
                q.push({ii,jj,w+1});
            }
        }
    }
    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        cout<<t[i][j]<<' ';
        cout<<endl;
    }*/
    int dist[n][n];
    int l=-1,r=n*n;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        memset(dist,-1,sizeof dist);
        queue<e> qq;
        qq.push({mx,my,mid,ss});
        dist[mx][my]=mid;
        while(!qq.empty())
        {
            auto p=qq.front();
            qq.pop();
            int i=p.i,j=p.j,sec=p.sec,step=p.step;
            if(step==ss)
            {
                step=1;
                sec++;
            }
            else
            step++;
            //cout<<sec<<" ";
            for(int k=0;k<4;k++)
            {
                int ii=i+di[k],jj=j+dj[k];
                if(ii<0||ii>=n||jj<0||jj>=n)
                continue;
                if(dist[ii][jj]==-1)
                {
                    if((s[ii][jj]=='G'&&(t[ii][jj]>=sec||t[ii][jj]==-1))||s[ii][jj]=='D')
                    {
                        dist[ii][jj]=sec;
                        qq.push({ii,jj,sec,step});
                    }
                }
            }
        }
        //cout<<mid<<' ';
            if(dist[dx][dy]!=-1)
            l=mid;
            else
            r=mid-1;
            /*for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                cout<<dist[i][j]<<' ';
                cout<<endl;
            }*/
    }
    cout<<l;
}

• Subtask 1: 38 / 100