Submission #312965

#	Time	Username	Problem	Language	Result	Execution time	Memory
312965		fergonzgut21	Mecho (IOI09_mecho)	C++14	94 / 100	1083 ms	9164 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][2], rilres = -1;
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--;
        }
    }
}

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

int main()
{
    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] = -1;
            vis[i][j][0] = 32700;
            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();
    vis[sx][sy][1] = 32700;
    vis[sx][sy][0] = 0;
    solve2(sx, sy, 0, B[sx][sy] - 1);
    cout << rilres;
    return 0;
}

• Subtask 1: 94 / 100