Submission #637025

#	Time	Username	Problem	Language	Result	Execution time	Memory
637025		thienbao1602	Mecho (IOI09_mecho)	C++17	100 / 100	249 ms	11360 KiB

mecho

#include    <bits/stdc++.h>
#define ll long long
#define pi pair<ll, ll>
#define fi first
#define se second
using namespace std;

const int u[] = {0, 1, 0, -1};
const int v[] = {1, 0, -1, 0};

int n, steps;
char grid[805][805];
pi init, home;
vector<pi> honey;

bool check(ll cur, ll dist, ll m)
{
    if (cur % steps == 0)
    {
        return (cur / steps + m < dist);
    } else
    {
        return (cur / steps  + m + 1 <= dist);
    }
}

bool safe(int u, int v)
{
    return (u >= 0 && u < n && v >= 0 && v < n);
}

void solve()
{
    cin >> n >> steps;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> grid[i][j];
            if (grid[i][j] == 'M')
            {
                init = make_pair(i, j);
            }

            if (grid[i][j] == 'D')
            {
                home = make_pair(i, j);
            }

            if (grid[i][j] == 'H')
            {
                honey.push_back({i, j});
            }
        }
    }

    vector<vector<ll>> dist1(n, vector<ll>(n, -1));
    queue<pi> que;
    for(pi x : honey)
    {
        que.push(x);
        dist1[x.fi][x.se] = 0;
    }

    while(!que.empty())
    {
        pi now = que.front(); que.pop();
        int curU = now.fi, curV = now.se;
        for(int i=0; i<4; i++)
        {
            int ux = u[i] + curU, vx = v[i] + curV;
            if (safe(ux, vx) && (grid[ux][vx] == 'G' || grid[ux][vx] == 'M') && dist1[ux][vx] == -1)
            {
                dist1[ux][vx] = dist1[curU][curV] + 1;
                que.push({ux, vx});
            }
        }
    }

    ll l = 0, r = 1e9;
    ll ans =  -1;
    while(l <= r)
    {
        ll m = (l + r) >> 1;
        que.push(init);
        vector<vector<ll>> dis(n, vector<ll>(n, -1));
        dis[init.fi][init.se] = 0;

        if (m < dist1[init.fi][init.se])
        {
            while(!que.empty())
            {
                pi now = que.front(); que.pop();
                int curU = now.fi, curV = now.se;
                for(int i=0; i<4; i++)
                {
                    int ux = curU + u[i], vx = curV + v[i];
                    if (ux == home.fi && vx == home.se)
                    {
                        dis[ux][vx] = dis[curU][curV] + 1;
                        break;
                    }

                    if (safe(ux, vx) && grid[ux][vx] != 'H' && dis[ux][vx] == -1 && check(dis[curU][curV] + 1, dist1[ux][vx], m))
                    {
                        dis[ux][vx] = dis[curU][curV] + 1;
                        que.push({ux, vx});
                    }
                }
            }
        }

        if (dis[home.fi][home.se] == -1)
        {
            r = m - 1;
        } else
        {
            ans = m;
            l = m + 1;
        }
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 100 / 100