Submission #888542

#	Time	Username	Problem	Language	Result	Execution time	Memory
888542		Billy_Nguyen	Mecho (IOI09_mecho)	C++17	6 / 100	124 ms	27680 KiB

mecho

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

#define x first
#define fastio()                 \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004;  // Modular inverse of 2 modulo (10^9 + 7), also
                                // the number has to be in long long otherwise
                                // if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
vector<vector<char>> grid;
ll n, s;
pair<ll, ll> bear, home;
vector<pair<ll, ll>> hives;
vector<vector<ll>> beesDepths;
vector<vector<ll>> bearDepths;
bool valid = false;

void floodfill(ll i, ll j, vector<vector<bool>> &visited, ll mins) {
    REP(k, 0, 4) {
        if (i + dy[k] < 1 || j + dx[k] < 1 || i + dy[k] > n || j + dx[k] > n) {
            continue;
        }

        if (visited[i + dy[k]][j + dx[k]]) {
            continue;
        }

        if ((bearDepths[i + dy[k]][j + dx[k]] + 1) / s >=
            beesDepths[i + dy[k]][j + dx[k]] - mins) {
            continue;
        }

        if (grid[i + dy[k]][j + dx[k]] == 'D') {
            valid = true;
            return;
        }

        if (grid[i + dy[k]][j + dx[k]] != 'G') {
            continue;
        }

        visited[i][j] = true;
        floodfill(i + dy[k], j + dx[k], visited, mins);
    }
}

void solve() {
    cin >> n >> s;

    grid.resize(n + 1);
    beesDepths.resize(n + 1);

    REP(i, 0, n + 1) {
        grid[i].resize(n + 1);
        beesDepths[i].resize(n + 1, 1e18);
    }

    REP(i, 1, n + 1) {
        REP(j, 1, n + 1) {
            cin >> grid[i][j];

            if (grid[i][j] == 'M') {
                bear = {i, j};
            }

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

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

    deque<pair<pair<ll, ll>, ll>> q;

    REP(i, 0, hives.size()) {
        q.PB(MP(hives[i], 0));
        beesDepths[hives[i].x][hives[i].y] = 0;
    }

    while (!q.empty()) {
        pair<pair<ll, ll>, ll> cur = q.front();
        pair<ll, ll> coords = cur.x;
        ll d = cur.y;
        q.pop_front();

        REP(k, 0, 4) {
            if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
                coords.x + dy[k] > n || coords.y + dy[k] > n ||
                (grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' &&
                 grid[coords.x + dy[k]][coords.y + dx[k]] != 'D' && grid[coords.x + dy[k]][coords.y + dx[k]] != 'M')) {
                continue;
            }

            if (beesDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) {
                beesDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
                q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
            }
        }
    }

    ll l = 0;
    ll r = n * n;
    q.PB(MP(bear, 0));
    bearDepths.resize(n + 1);

    REP(i, 0, n + 1) { bearDepths[i].resize(n + 1, 1e18); }
    bearDepths[bear.x][bear.y] = 0;

    while (!q.empty()) {
        pair<pair<ll, ll>, ll> cur = q.front();
        q.pop_front();

        pair<ll, ll> coords = cur.x;
        ll d = cur.y;

        REP(k, 0, 4) {
            if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
                coords.x + dy[k] > n || coords.y + dy[k] > n ||
                (grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' &&
                 grid[coords.x + dy[k]][coords.y + dx[k]] != 'D')) {
                continue;
            }

            if (bearDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) {
                bearDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
                q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
            }
        }
    }

    while (l <= r) {
        ll mid = l + (r - l) / 2;
        vector<vector<bool>> bearVis(n + 1);

        REP(i, 0, n + 1) { bearVis[i].resize(n + 1, false); }

        bearVis[bear.x][bear.y] = true;

        floodfill(bear.x, bear.y, bearVis, mid);
        if (valid) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }

        // cout << l << " " << r << "\n";
    }

    cout << l - 1 << "\n";
}

int main() {
    fastio();
    solve();

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:32:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 | #define REP(i, a, b) for (int i = a; i < b; i++)
......
  109 |     REP(i, 0, hives.size()) {
      |         ~~~~~~~~~~~~~~~~~~              
mecho.cpp:109:5: note: in expansion of macro 'REP'
  109 |     REP(i, 0, hives.size()) {
      |     ^~~

• Subtask 1: 6 / 100