Submission #1162570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162570		AlgorithmWarrior	Mecho (IOI09_mecho)	C++20	100 / 100	360 ms	3996 KiB

mecho

#include <bits/stdc++.h>
#define MAX 805

using namespace std;

char mat[MAX][MAX];
int drum[MAX][MAX];
int N,S;
struct point
{
    int l,c,niv;
};
queue<point>bear;
queue<point>bee;
int homeL,homeC;

void read()
{
    cin>>N>>S;
    int i,j;
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
        {
            cin>>mat[i][j];
            if(mat[i][j]=='D')
            {
                homeL=i;
                homeC=j;
            }
        }
}

int dl[]={-1,0,1,0};
int dc[]={0,1,0,-1};
bool continua;

void expand_bee()
{
    int niv=(bee.empty())?0:bee.front().niv;
    while(!bee.empty() && bee.front().niv==niv)
    {
        point curr=bee.front();
        bee.pop();
        int i;
        for(i=0;i<4;++i)
        {
            int lnou=curr.l+dl[i];
            int cnou=curr.c+dc[i];
            if((mat[lnou][cnou]=='G' || mat[lnou][cnou]=='M') && drum[lnou][cnou]>=0)
            {
                drum[lnou][cnou]=niv-1;
                bee.push({lnou,cnou,niv-1});
                continua=1;
            }
        }
    }
}

void expand_bear()
{
    int niv=(bear.empty())?0:bear.front().niv;
    while(!bear.empty() && bear.front().niv<niv+S)
    {
        point curr=bear.front();
        bear.pop();
        if(drum[curr.l][curr.c]<0)
            continue;
        int i;
        for(i=0;i<4;++i)
        {
            int lnou=curr.l+dl[i];
            int cnou=curr.c+dc[i];
            if((mat[lnou][cnou]=='G' || mat[lnou][cnou]=='D') && !drum[lnou][cnou])
            {
                drum[lnou][cnou]=curr.niv+1;
                bear.push({lnou,cnou,curr.niv+1});
                continua=1;
            }
        }
    }
}

bool check(int nr)
{
    int i,j;
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
            if(mat[i][j]=='M')
            {
                drum[i][j]=1;
                bear.push({i,j,1});
            }
            else
                if(mat[i][j]=='H')
                {
                    drum[i][j]=-1;
                    bee.push({i,j,-1});
                }
    for(i=1;i<=nr;++i)
        expand_bee();
    continua=1;
    while(continua)
    {
        continua=0;
        expand_bear();
        expand_bee();
    }
    int rasp=drum[homeL][homeC];
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
            drum[i][j]=0;
    while(!bee.empty())
        bee.pop();
    while(!bear.empty())
        bear.pop();
    return rasp>0;
}

int bin_search()
{
    int left=-1;
    int right=N*N;
    while(right-left>1)
    {
        int mid=(left+right)/2;
        if(check(mid))
            left=mid;
        else
            right=mid;
    }
    return left;
}

void write()
{
    cout<<bin_search();
}

int main()
{
    read();
    write();
    return 0;
}

• Subtask 1: 100 / 100