Submission #1205713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205713		newsboy	Mecho (IOI09_mecho)	C++20	100 / 100	771 ms	27476 KiB

mecho

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <list>
#include <random>
#include <initializer_list>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ld inf = 1e18;
constexpr ll N = 15;
constexpr ll MIN = -inf;
constexpr ll MAX = inf;

vector<ll> dx{ 0, 0, 1, -1 };
vector<ll> dy{ 1, -1, 0, 0 };

struct T {
    ll x, y;
};

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<string> a(n);
    T s = { MAX, MAX }, f = { MAX, MAX };
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
        for (ll j = 0; j < n; ++j) {
            if (a[i][j] == 'M') {
                s = { i, j };
            }
            else if (a[i][j] == 'D') {
                f = { i, j };
            }
        }
    }
    queue<T> q;
    vector<vector<ll>> dh(n, vector<ll>(n, MAX));
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            if (a[i][j] == 'H') {
                dh[i][j] = 0;
                q.push({ i, j });
            }
        }
    }
    auto ok = [&](ll x, ll y) -> bool {
        return x >= 0 && x < n && y >= 0 && y < n;
        };
    while (!q.empty()) {
        T v = q.front();
        q.pop();
        for (ll i = 0; i < 4; ++i) {
            ll x = v.x + dx[i], y = v.y + dy[i];
            if (ok(x, y) && (a[x][y] == 'G' || a[x][y] == 'M') && dh[x][y] == MAX) {
                dh[x][y] = dh[v.x][v.y] + 1;
                q.push({ x, y });
            }
        }
    }
    auto upgrade = [&](vector<string>& a, ll M) -> vector<string> {
        auto b = a;
        for (ll i = 0; i < n; ++i) {
            for (ll j = 0; j < n; ++j) {
                if (dh[i][j] <= M) {
                    b[i][j] = 'H';
                }
            }
        }
        return b;
        };
    auto check = [&](vector<string>& a) -> bool {
        queue<T> q;
        vector<vector<ll>> d1(n, vector<ll>(n, MAX));
        for (ll i = 0; i < n; ++i) {
            for (ll j = 0; j < n; ++j) {
                if (a[i][j] == 'H') {
                    d1[i][j] = 0;
                    q.push({ i, j });
                }
            }
        }
        while (!q.empty()) {
            T v = q.front();
            q.pop();
            for (ll i = 0; i < 4; ++i) {
                ll x = v.x + dx[i], y = v.y + dy[i];
                if (ok(x, y) && (a[x][y] == 'G' || a[x][y] == 'M') && d1[x][y] == MAX) {
                    d1[x][y] = d1[v.x][v.y] + 1;
                    q.push({ x, y });
                }
            }
        }
        vector<vector<ll>> d2(n, vector<ll>(n, MAX));
        vector<vector<ll>> mod(n, vector<ll>(n, MAX));
        q.push(s);
        d2[s.x][s.y] = 0;
        if (a[s.x][s.y] == 'H') {
            return 0;
        }
        while (!q.empty()) {
            T v = q.front();
            q.pop();
            for (ll i = 0; i < 4; ++i) {
                ll x = v.x + dx[i], y = v.y + dy[i];
                if (ok(x, y) && a[x][y] == 'G' && d2[x][y] == MAX) {
                    d2[x][y] = d2[v.x][v.y] + 1;
                    q.push({ x, y });
                }
            }
        }
        for (ll i = 0; i < n; ++i) {
            for (ll j = 0; j < n; ++j) {
                if (d2[i][j] != MAX) {
                    mod[i][j] = d2[i][j] % k;
                    d2[i][j] = (d2[i][j] + k - 1) / k;
                }
            }
        }
        vector<vector<bool>> possible(n, vector<bool> (n));
        for (ll i = 0; i < n; ++i) {
            for (ll j = 0; j < n; ++j) {
                possible[i][j] = (a[i][j] == 'G' && (d2[i][j] < d1[i][j] || (d2[i][j] == d1[i][j] && mod[i][j] != 0)));
            }
        }
        q.push(s);
        vector<vector<ll>> vis(n, vector<ll> (n));
        vis[s.x][s.y] = 1;
        while (!q.empty()) {
            T v = q.front();
            q.pop();
            for (ll i = 0; i < 4; ++i) {
                ll x = v.x + dx[i], y = v.y + dy[i];
                if (ok(x, y) && a[x][y] == 'G' && !vis[x][y] && possible[x][y]) {
                    vis[x][y] = 1;
                    q.push({ x, y });
                }
            }
        }
        ll ans = 0;
        for (ll i = 0; i < 4; ++i) {
            ll x = f.x + dx[i], y = f.y + dy[i];
            if (ok(x, y) && vis[x][y] && (d2[x][y] < d1[x][y] || (d2[x][y] == d1[x][y] && mod[x][y] != 0))) {
                ans |= 1;
            }
        }
        /*for (ll i = 0; i < n; ++i) {
            for (ll j = 0; j < n; ++j) {
                cout << possible[i][j] << " \n"[j == n - 1];
            }
        }*/
        return ans;
        };
    ll L = 0, R = 1e6;
    while (R - L > 1) {
        ll M = (L + R) / 2;
        auto b = upgrade(a, M);
        if (check(b)) {
            L = M;
        }
        else {
            R = M;
        }
    }
    cout << (check(a) ? L : -1) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    /*cin >> t;*/
    while (t--) {
        solve();
    }
    return 0;
}
//4 1
//MGDG
//GGGG
//GGGG
//GGGH

• Subtask 1: 100 / 100