Submission #646194

#	Time	Username	Problem	Language	Result	Execution time	Memory
646194		Pyrodox	Mecho (IOI09_mecho)	C++17	26 / 100	1097 ms	31688 KiB

mecho

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

const ll mx = 801;
ll n, s, startr, startc, endr, endc;

vector<vector<char>> grid(mx, vector<char>(mx));
vector<pair<ll, ll>> bees;
vector<vector<ll>> beevis(mx, vector<ll>(mx, -1));

void bfs()
{
    queue<vector<ll>> que;
    que.push({startr, startc, 0, mx * mx});
    vector<vector<ll>> depth(mx, vector<ll>(mx, -1));
    depth[startr][startc] = mx * mx;
    ll ans = -1;
    auto check = [&](ll newx, ll newy, ll truemoves, ll keepmin)
    {
        if (newx < n && newx >= 0 && newy < n && newy >= 0 && grid[newx][newy] != 'T' && 
        (grid[newx][newy] == 'D' || (truemoves / s + 1 <= beevis[newx][newy] && (truemoves + 1) % s) || (truemoves / s + 1 < beevis[newx][newy] && (truemoves + 1) % s == 0))) {
            ll dif = beevis[newx][newy] - (truemoves / s + 1);
            if (grid[newx][newy] == 'D') {
                dif = mx * mx;
            }
            ll a = min(keepmin, dif);
            if (grid[newx][newy] == 'D' || dif > depth[newx][newy] || depth[newx][newy] == -1) {
                if (grid[newx][newy] != 'D') {
                    que.push({newx, newy, truemoves + 1, a});
                }
                else {
                    ans = max(ans, a);
                }
                depth[newx][newy] = dif;
            }
        }
    };
    while (que.size()) {
        ll x = que.front()[0], y = que.front()[1], truemoves = que.front()[2], keepmin = que.front()[3];
        //cout << x << " " << y << " " << truemoves << " " << keepmin << "\n";
        que.pop();
        check(x + 1, y, truemoves, keepmin);
        check(x - 1, y, truemoves, keepmin);
        check(x, y + 1, truemoves, keepmin);
        check(x, y - 1, truemoves, keepmin);
    }
    cout << ans;
}

void floodfill(ll r, ll c, ll fillval)
{
    if (r < 0 || r >= n || c < 0 || c >= n || (beevis[r][c] <= fillval && fillval && beevis[r][c] != -1) || grid[r][c] == 'T' || grid[r][c] == 'D') {
        return;
    }
    beevis[r][c] = fillval;
    floodfill(r - 1, c, fillval + 1);
    floodfill(r + 1, c, fillval + 1);
    floodfill(r, c - 1, fillval + 1);
    floodfill(r, c + 1, fillval + 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'M') {
                startr = i;
                startc = j;
            }
            else if (grid[i][j] == 'D') {
                endr = i;
                endc = j;
            }
            else if (grid[i][j] == 'H') {
                bees.push_back({i, j});
                beevis[i][j] = 0;
            }
        }
    }
    for (ll i = 0; i < bees.size(); ++i) {
        floodfill(bees[i].first, bees[i].second, 0);
    }
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            //cout << beevis[i][j] << " ";
        }
        //cout << "\n";
    }
    bfs();
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:85:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (ll i = 0; i < bees.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 26 / 100