Submission #1155948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155948		vicvic	Mecho (IOI09_mecho)	C++20	76 / 100	235 ms	19632 KiB

mecho

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int bulan=6400;
const int dx[]={0, 0, -1, 1};
const int dy[]={-1, 1, 0, 0};
int n, s, ok;
int viz[805][805], blocked[805][805], xs, ys, ye, xe, viz2[805][805];
char mat[805][805];
vector <pair <int, int>> initial, trees;
queue <pair <int, int>> coadab[bulan+5];
queue <vector <int>> coada[bulan+5];
bool ismat (int i, int j)
{
    return i>=1 && j>=1 && i<=n && j<=n;
}
void moveBees (int time)
{
    while (!coadab[time].empty())
    {
        int x=coadab[time].front().first;
        int y=coadab[time].front().second;
        coadab[time].pop();
        blocked[x][y]=1;
        for (int i=0;i<=3;i++)
        {
            int inou=dx[i]+x;
            int jnou=dy[i]+y;
            if (ismat (inou, jnou) && !viz[inou][jnou] && (mat[inou][jnou]=='G' || mat[inou][jnou]=='M'))
            {
                viz[inou][jnou]=1;
                coadab[time+1].push ({inou, jnou});
            }
        }
    }
}
void moveBear (int time)
{
    while (!coada[time].empty())
    {
        int x=coada[time].front()[0];
        int y=coada[time].front()[1];
        int step=coada[time].front()[2];
        coada[time].pop();
        if (blocked[x][y])
            continue;
        if (x==xe && y==ye)
            ok=1;
        for (int i=0;i<=3;i++)
        {
            int inou=dx[i]+x;
            int jnou=dy[i]+y;
            if (ismat (inou, jnou) && !viz2[inou][jnou] && !blocked[inou][jnou] && (mat[inou][jnou]=='G' || mat[inou][jnou]=='D'))
            {
                viz2[inou][jnou]=1;
                if (step==s-1)
                {
                    coada[time+1].push ({inou, jnou, 0});
                }
                else coada[time].push ({inou, jnou, step+1});
            }
        }
    }
}
bool check (int val)
{
    ok=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            viz[i][j]=0;
            viz2[i][j]=0;
            blocked[i][j]=0;
        }
    }
    for (int i=0;i<=bulan+1;i++)
    {
        while (!coada[i].empty())
        {
            coada[i].pop();
        }
        while (!coadab[i].empty())
        {
            coadab[i].pop();
        }
    }
    coada[val+1].push ({xs, ys, 0});
    viz2[xs][ys]=1;
    for (auto tree : trees)
    {
        blocked[tree.first][tree.second]=1;
    }
    for (auto poz : initial)
    {
        viz[poz.first][poz.second]=1;
        coadab[0].push ({poz.first, poz.second});
    }
    moveBees (0);
    for (int crt_time=1;;crt_time++)
    {
        if (crt_time>val && coada[crt_time].empty())
            return 0;
        if (crt_time>val) moveBear (crt_time);
        if (ok)
        {
            break;
        }
        moveBees (crt_time);
    }
    return 1;
}
int main ()
{
    cin >> n >> s;
    for (int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        for (int j=1;j<=n;j++)
        {
            mat[i][j]=s[j-1];
            if (mat[i][j]=='T')
            {
                trees.push_back ({i, j});
            }
            if (mat[i][j]=='H')
            {
                initial.push_back ({i, j});
            }
            if (mat[i][j]=='M')
            {
                xs=i;
                ys=j;
            }
            if (mat[i][j]=='D')
            {
                ye=j;
                xe=i;
            }
        }
    }
    int st=0, dr=bulan+1, poz=-1;
    while (st<=dr)
    {
        int mij = (st+dr) >> 1;
        if (check (mij))
        {
            st=mij+1;
            poz=mij;
        }
        else dr=mij-1;
    }
    cout << poz;
    return 0;
}

• Subtask 1: 76 / 100