제출 #1155972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155972		vicvic	Mecho (IOI09_mecho)	C++20	97 / 100	688 ms	11380 KiB

mecho

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int bulan=300000;
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 <vector <int>> coadab;
queue <vector <int>> coada;
bool ismat (int i, int j)
{
    return i>=1 && j>=1 && i<=n && j<=n;
}
void moveBees (int time)
{
    while (!coadab.empty())
    {
        int x=coadab.front()[0];
        int y=coadab.front()[1];
        int val=coadab.front()[2];
        if (val>time)
            break;
        coadab.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.push ({inou, jnou, val+1});
            }
        }
    }
}
void moveBear (int time)
{
    while (!coada.empty())
    {
        int x=coada.front()[0];
        int y=coada.front()[1];
        int step=coada.front()[2];
        if (step>s*time)
            break;
        coada.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;
                coada.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;
        }
    }
    coada.push ({xs, ys, 1});
    viz2[xs][ys]=1;
    for (auto tree : trees)
    {
        blocked[tree.first][tree.second]=1;
        viz[tree.first][tree.second]=1;
    }
    for (auto poz : initial)
    {
        viz[poz.first][poz.second]=1;
        coadab.push ({poz.first, poz.second, 0});
    }
    moveBees (0);
    int mx=0;
    for (int crt_time=1;;crt_time++)
    {
        mx=crt_time;
        if (coada.empty())
            break;
        if (crt_time>val) moveBear (crt_time-val);
        if (ok)
        {
            break;
        }
        moveBees (crt_time);
    }
    while (!coada.empty())
        coada.pop();
    while (!coadab.empty())
        coadab.pop();
    return ok;
}
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: 97 / 100