Submission #313370

#	Time	Username	Problem	Language	Result	Execution time	Memory
313370		fergonzgut21	Mecho (IOI09_mecho)	C++14	100 / 100	170 ms	7040 KiB

mecho

#include <iostream>
#include <queue>
#define MAX 802
using namespace std;

struct bee
{
    short int x;
    short int y;
    int t;
    int r;
};

int N, S, sx, sy, ex, ey, B[MAX][MAX], vis[MAX][MAX], l, r, mid, res, cur;
bool xd;
char A[MAX][MAX];
queue <bee> qiu;
bee temp;

void solve ()
{
    while (!qiu.empty())
    {
        temp = qiu.front();
        qiu.pop();
        temp.t++;
        if (B[temp.x - 1][temp.y] == -1 && A[temp.x - 1][temp.y] != 'T' && A[temp.x - 1][temp.y] != 'D')
        {
            B[temp.x - 1][temp.y] = temp.t;
            temp.x--;
            qiu.push(temp);
            temp.x++;
        }
        if (B[temp.x + 1][temp.y] == -1 && A[temp.x + 1][temp.y] != 'T' && A[temp.x + 1][temp.y] != 'D')
        {
            B[temp.x + 1][temp.y] = temp.t;
            temp.x++;
            qiu.push(temp);
            temp.x--;
        }
        if (B[temp.x][temp.y - 1] == -1 && A[temp.x][temp.y - 1] != 'T' && A[temp.x][temp.y - 1] != 'D')
        {
            B[temp.x][temp.y - 1] = temp.t;
            temp.y--;
            qiu.push(temp);
            temp.y++;
        }
        if (B[temp.x][temp.y + 1] == -1 && A[temp.x][temp.y + 1] != 'T' && A[temp.x][temp.y + 1] != 'D')
        {
            B[temp.x][temp.y + 1] = temp.t;
            temp.y++;
            qiu.push(temp);
            temp.y--;
        }
    }
}

bool solve2(int x, int y, int t, int r)
{
    if (r == -1)
        return 1;
    temp.x = x;
    temp.y = y;
    temp.t = t;
    temp.r = r;
    qiu.push(temp);
    while (!qiu.empty())
    {
        temp = qiu.front();
        qiu.pop();
        //cout << temp.x << " " << temp.y << " " << temp.t << " " << temp.r << endl;
        if (temp.x == ex && temp.y == ey)
            return 1;
        if (temp.r + (temp.t / S) >= B[temp.x][temp.y])
            continue;
        temp.t++;
        if (vis[temp.x + 1][temp.y] < cur && A[temp.x + 1][temp.y] != 'T')
        {
                vis[temp.x + 1][temp.y] = cur;
                temp.x++;
                qiu.push(temp);
                temp.x--;
        }
        if (vis[temp.x - 1][temp.y] < cur && A[temp.x - 1][temp.y] != 'T')
        {
                vis[temp.x - 1][temp.y] = cur;
                temp.x--;
                qiu.push(temp);
                temp.x++;
        }
        if (vis[temp.x][temp.y + 1] < cur && A[temp.x][temp.y + 1] != 'T')
        {
                vis[temp.x][temp.y + 1] = cur;
                temp.y++;
                qiu.push(temp);
                temp.y--;
        }
        if (vis[temp.x][temp.y - 1] < cur && A[temp.x][temp.y - 1] != 'T')
        {
                vis[temp.x][temp.y - 1] = cur;
                temp.y--;
                qiu.push(temp);
                temp.y++;
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> S;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            cin >> A[i][j];
            vis[i][j] = -1;
            B[i][j] = -1;
            if (A[i][j] == 'M')
            {
                sx = i;
                sy = j;
            }
            if (A[i][j] == 'D')
            {
                ex = i;
                ey = j;
            }
            if (A[i][j] == 'H')
            {
                temp.x = i;
                temp.y = j;
                temp.t = 0;
                B[i][j] = 0;
                qiu.push(temp);
            }
        }
    solve();
    l = -1;
    r = 650000;
    while (l <= r)
    {
        mid = (l + r) / 2;
        cur++;
        vis[sx][sy] = cur;
        while (!qiu.empty())
            qiu.pop();
        xd = solve2(sx, sy, 0, mid);
        if (xd == 1)
        {
            res = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    cout << res;
    return 0;
}

• Subtask 1: 100 / 100