Submission #1308639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308639		zadniprovska	Mecho (IOI09_mecho)	C++20	10 / 100	515 ms	23500 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
 
const ll DIM = 800 + 7;
const ll INF = 1e18;
const ll mod = 998244353;
const ll maxlog = 20;
const ll bsize = 350;

char c[DIM][DIM];
ll dist[DIM][DIM], dist2[DIM][DIM];
vector<pll> bees;
ll sti, stj, fi, fj;
ll n, s;


bool can (ll x) {

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            dist[i][j] = INF;
        }
    }

    queue<pll> q;
    for (auto [i, j] : bees) {
        q.push({i, j});
        dist[i][j] = 0;
    }
    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();

        if (dist[i][j] == x) continue;

        if (i>1 && c[i-1][j]!='T' && c[i-1][j]!='D' && dist[i-1][j] == INF) {
            dist[i-1][j] = dist[i][j] + 1;
            q.push({i-1, j});
        }
        if (i<n && c[i+1][j]!='T' && c[i+1][j]!='D' && dist[i+1][j] == INF) {
            dist[i+1][j] = dist[i][j] + 1;
            q.push({i+1, j});
        }
        if (j>1 && c[i][j-1]!='T' && c[i][j-1]!='D' && dist[i][j-1] == INF) {
            dist[i][j-1] = dist[i][j] + 1;
            q.push({i, j-1});
        }
        if (j<n && c[i][j+1]!='T' && c[i][j+1]!='D' && dist[i][j+1] == INF) {
            dist[i][j+1] = dist[i][j] + 1;
            q.push({i, j+1});
        }
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (dist[i][j] != INF) {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();

        if (i>1 && c[i-1][j]!='T' && c[i-1][j]!='D' && dist[i-1][j] == INF) {
            dist[i-1][j] = dist[i][j] + 1;
            q.push({i-1, j});
        }
        if (i<n && c[i+1][j]!='T' && c[i+1][j]!='D' && dist[i+1][j] == INF) {
            dist[i+1][j] = dist[i][j] + 1;
            q.push({i+1, j});
        }
        if (j>1 && c[i][j-1]!='T' && c[i][j-1]!='D' && dist[i][j-1] == INF) {
            dist[i][j-1] = dist[i][j] + 1;
            q.push({i, j-1});
        }
        if (j<n && c[i][j+1]!='T' && c[i][j+1]!='D' && dist[i][j+1] == INF) {
            dist[i][j+1] = dist[i][j] + 1;
            q.push({i, j+1});
        }
    }


    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            dist2[i][j] = INF;
        }
    }
    dist2[sti][stj] = 0;
    q.push({sti, stj});

    while (!q.empty()) {

        auto [i, j] = q.front(); q.pop();
        if (i == fi && j == fj) break;

        vector< pair<pll, ll> > vec;
        vec.pb({{i, j}, 0});
        ll p = 0;
        while (p < vec.size()) {

            auto [coord, step] = vec[p];
            p++;
            ll i2 = coord.ff, j2 = coord.ss;

            //cout << "// " << i2 << " " << j2 << endl;

            if (step == s) continue;

            if (i2>1 && c[i2-1][j2]!='T' && dist2[i2-1][j2] == INF && (dist2[i][j]+1) <= dist[i2-1][j2]) {
                dist2[i2-1][j2] = dist2[i][j] + 1;
                vec.pb({{i2-1, j2}, step+1});
                q.push({i2-1, j2});
            }
            if (i2<n && c[i2+1][j2]!='T' && dist2[i2+1][j2] == INF && (dist2[i][j]+1) <= dist[i2+1][j2]) {
                dist2[i2+1][j2] = dist2[i][j] + 1;
                vec.pb({{i2+1, j2}, step+1});
                q.push({i2+1, j2});
            }
            if (j2>1 && c[i2][j2-1]!='T' && dist2[i2][j2-1] == INF && (dist2[i][j]+1) <= dist[i2][j2-1]) {
                dist2[i2][j2-1] = dist2[i][j] + 1;
                vec.pb({{i2, j2-1}, step+1});
                q.push({i2, j2-1});
            }
            if (j2<n && c[i2][j2+1]!='T' && dist2[i2][j2+1] == INF && (dist2[i][j]+1) <= dist[i2][j2+1]) {
                dist2[i2][j2+1] = dist2[i][j] + 1;
                vec.pb({{i2, j2+1}, step+1});
                q.push({i2, j2+1});
            }

        }


    }

    /*for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (dist[i][j] == INF) cout << "- ";
            else cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (dist2[i][j] == INF) cout << "- ";
            else cout << dist2[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;*/

    return (dist2[fi][fj] != INF);


}

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

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            dist[i][j] = INF;
        }
    }

    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {

            cin >> c[i][j];

            if (c[i][j] == 'M') sti = i, stj = j;
            else if (c[i][j] == 'D') fi = i, fj = j;
            else if (c[i][j] == 'H') {
                bees.pb({i, j});
                dist[i][j] = 0;
            }

        }
    }

    ll L = 0, R = n;
    while (L < R) {

        ll mid = (L + R + 1) >> 1;

        //cout << "/ " << mid << endl;
        //cout << can(mid) << endl;

        if (can(mid)) L = mid;
        else R = mid-1;

    }


    

    if (can(L)) cout << L << endl;
    else cout << -1 << endl;

}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("atlarge.in", "r", stdin);
    //freopen("atlarge.out", "w", stdout);
 
    int ntest = 1;
    //cin >> ntest;
    while (ntest--) {
        solve();
    }
    return 0;
 
}
;

• Subtask 1: 10 / 100