Submission #960576

#	Time	Username	Problem	Language	Result	Execution time	Memory
960576		htphong0909	Mecho (IOI09_mecho)	C++17	95 / 100	158 ms	17628 KiB

mecho

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

char arr[1001][1001];
int n, s;
int stx, sty, ex, ey;
bool in(int x, int y)
{
    return (min(x, y) >= 1 && max(x, y) <= n);
}

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int dBee[1001][1001];
int D[1001][1001];

bool check(int mid)
{
    memset(D, 0x3f, sizeof D);
    D[stx][sty] = mid * s;
    queue<pair<int, int>> q;
    q.emplace(stx, sty);
    while (!q.empty())
    {
        int ux, uy;
        tie(ux, uy) = q.front();
        q.pop();

        if (D[ux][uy] >= dBee[ux][uy]) continue;

        for (int i = 0; i < 4; i++)
        {
            int vx = ux + dx[i];
            int vy = uy + dy[i];
            if (in(vx, vy) && arr[vx][vy] != 'T' && D[vx][vy] > D[ux][uy] + 1)
            {
                D[vx][vy] = D[ux][uy] + 1;
                q.emplace(vx, vy);
            }
        }
    }
    if (D[ex][ey] < (int)1e18) return true;
    else return false;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("TEST.IN", "r", stdin);
    //freopen("TEST.OUT", "w", stdout);
    cin >> n >> s;
    queue<pair<int, int>> q;
    memset(dBee, 0x3f, sizeof dBee);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 'H')
            {
                q.emplace(i, j);
                dBee[i][j] = 0;
            }
            if (arr[i][j] == 'M')
            {
                tie(stx, sty) = make_pair(i, j);
            }
            if (arr[i][j] == 'D')
            {
                tie(ex, ey) = make_pair(i, j);
            }
        }
    }
    while (!q.empty())
    {
        int ux, uy;
        tie(ux, uy) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int vx = ux + dx[i];
            int vy = uy + dy[i];
            if (in(vx, vy) && arr[vx][vy] != 'T' && dBee[vx][vy] > dBee[ux][uy] + s)
            {
                dBee[vx][vy] = dBee[ux][uy] + s;
                q.emplace(vx, vy);
            }
        }
    }
    int l = 0;
    int r = 1e9;
    int ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans;
    return 0;
}

• Subtask 1: 95 / 100