Submission #893254

#	Time	Username	Problem	Language	Result	Execution time	Memory
893254		maxFedorchuk	Mecho (IOI09_mecho)	C++14	100 / 100	352 ms	13552 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

const long long MX=850;
char ch[MX][MX];

long long bdg[MX][MX];
long long mech[MX][MX];

long long n,k;

long long homex;
long long homey;

queue < pair < long long , long long > > qb;
queue < pair < long long , long long > > qm;

long long corx[4]={0,0,1,-1};
long long cory[4]={1,-1,0,0};

void cn1()
{
    if(qb.empty())
    {
        return;
    }

    long long zrzn=bdg[qb.front().first][qb.front().second];

    while(!qb.empty())
    {
        long long zarx=qb.front().first;
        long long zary=qb.front().second;

        if(bdg[zarx][zary]!=zrzn)
        {
            return;
        }

        qb.pop();

        for(long long i=0;i<4;i++)
        {
            if(!bdg[zarx+corx[i]][zary+cory[i]] && (ch[zarx+corx[i]][zary+cory[i]]=='G' || ch[zarx+corx[i]][zary+cory[i]]=='M'))
            {
                bdg[zarx+corx[i]][zary+cory[i]]=bdg[zarx][zary]+1;
                qb.push({zarx+corx[i],zary+cory[i]});
            }
        }
    }

    return;
}

bool cn2()
{
    while(!qm.empty())
    {
        if(bdg[qm.front().first][qm.front().second])
        {
            qm.pop();
        }
        else
        {
            break;
        }
    }

    if(qm.empty())
    {
        return 0;
    }

    long long zrzn=mech[qm.front().first][qm.front().second]+k;

    while(!qm.empty())
    {
        long long zarx=qm.front().first;
        long long zary=qm.front().second;

        if(mech[zarx][zary]>=zrzn)
        {
            return 1;
        }

        qm.pop();

        if(bdg[zarx][zary])
        {
            continue;
        }

        for(long long i=0;i<4;i++)
        {
            if(!mech[zarx+corx[i]][zary+cory[i]] && !bdg[zarx+corx[i]][zary+cory[i]] && (ch[zarx+corx[i]][zary+cory[i]]=='G' || ch[zarx+corx[i]][zary+cory[i]]=='D'))
            {
                mech[zarx+corx[i]][zary+cory[i]]=mech[zarx][zary]+1;
                qm.push({zarx+corx[i],zary+cory[i]});
            }
        }

    }

    return 1;
}

bool can(long long zar)
{
    while(!qb.empty())
    {
        qb.pop();
    }
    while(!qm.empty())
    {
        qm.pop();
    }

    for(long long i=1;i<=n;i++)
    {
        for(long long j=1;j<=n;j++)
        {
            bdg[i][j]=0;
            mech[i][j]=0;

            if(ch[i][j]=='H')
            {
                bdg[i][j]=1;
                qb.push({i,j});
            }

            if(ch[i][j]=='M')
            {
                mech[i][j]=1;
                qm.push({i,j});
            }
        }
    }

    for(long long i=0;i<zar;i++)
    {
        cn1();
    }

    while(true)
    {
        if(!cn2())
        {
            return 0;
        }

        if(mech[homex][homey])
        {
            return 1;
        }

        cn1();
    }
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>k;

    for(long long i=0;i<=(n+1);i++)
    {
        for(long long j=0;j<=(n+1);j++)
        {
            ch[i][j]='T';
        }
    }

    for(long long i=1;i<=n;i++)
    {
        for(long long j=1;j<=n;j++)
        {
            cin>>ch[i][j];

            if(ch[i][j]=='D')
            {
                homex=i;
                homey=j;
            }
        }
    }

    long long l=0,r=n*n;

    while(l+1<r)
    {
        long long mid=(l+r)/2;

        if(can(mid))
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    }

    if(!can(l))
    {
        cout<<"-1\n";
        return 0;
    }

    cout<<l<<"\n";
    return 0;
}

• Subtask 1: 100 / 100