제출 #1305487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305487		Euclid73	Mecho (IOI09_mecho)	C++20	80 / 100	136 ms	11624 KiB

mecho

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

#define ll long long

const ll INF=1e12;
const ll MAXN=805;

/*
Multi-source bfs from all the hives to find out at which seconds every square isn't reachable
Now we want to find path from M to D.
For every second, we first have the bear move S squares then the bees
So given we go from time (for the bear its 1/s seconds each time and move 1 square) t*s to (t+1)*s, bear can only pass through squares with dist>t and ends at a square with dist >t+1

how to solve this now:
bin search on the starting t and from there bfs only to stuff that we can reach.
*/

ll n, s, sx, sy, ex, ey, db[MAXN][MAXN], dm[MAXN][MAXN], dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};
char grid[MAXN][MAXN];
queue<ll> q1, q2;

void bfsBees()
{
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            db[i][j]=INF;
            if (grid[i][j]=='H')
            {
                db[i][j]=0;
                q1.push(i);
                q2.push(j);
            }
        }
    }
    while (!q1.empty())
    {
        ll x=q1.front(), y=q2.front();
        q1.pop();
        q2.pop();
        for (int i=0; i<4; i++)
        {
            ll r=x+dx[i], c=y+dy[i];
            if (r>=0 && r<n && c>=0 && c<n && db[r][c]==INF && (grid[r][c]=='M' || grid[r][c]=='H' || grid[r][c]=='G'))
            {
                db[r][c]=db[x][y]+1;
                q1.push(r);
                q2.push(c);
            }
        }
    }
}

bool works(ll t)
{
    if (t>=db[sx][sy])
    {
        return 0;
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            dm[i][j]=INF;
        }
    }
    dm[sx][sy]=s*t;
    q1.push(sx);
    q2.push(sy);
    while (!q1.empty())
    {
        ll x=q1.front(), y=q2.front();
        q1.pop();
        q2.pop();
        for (int i=0; i<4; i++)
        {
            ll r=x+dx[i], c=y+dy[i];
            if (r>=0 && r<n && c>=0 && c<n && dm[r][c]==INF && (grid[r][c]=='M' || grid[r][c]=='D' || grid[r][c]=='G') && db[r][c]>(dm[x][y]+1)/s)
            {
                dm[r][c]=dm[x][y]+1;
                q1.push(r);
                q2.push(c);
            }
        }
    }
    return dm[ex][ey]!=INF;
}

int main()
{
    cin >> n >> s;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            cin >> grid[i][j];
            if (grid[i][j]=='M')
            {
                sx=i;
                sy=j;
            }
            if (grid[i][j]=='D')
            {
                ex=i;
                ey=j;
            }
        }
    }
    bfsBees();
    /*for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            cout << (db[i][j]==INF ? -1:db[i][j]) << " ";
        }
        cout << "\n";
    }
    cout << "\n";*/
    if (!works(0))
    {
        cout << "-1\n";
        return 0;
    }
    /*for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            cout << (dm[i][j]==INF ? -1:dm[i][j]) << " ";
        }
        cout << "\n";
    }
    cout << "\n";*/
    ll l=0, r=1e5, mid;
    while (l<r)
    {
        mid=(l+r+1)/2;
        if (works(mid))
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    cout << l << "\n";
}

• Subtask 1: 80 / 100