Submission #1306923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306923		samarthkulkarni	Mecho (IOI09_mecho)	C++20	84 / 100	157 ms	7116 KiB

mecho

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

#define ll int
#define vi vector<ll>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

const ll inf = 1e9;
ll n, s;
string a[810];
ll ti[810][810];
bool vis[810][810];
pr st, de;


pr operator+(pr p1, pr p2) {
    return {p1.ff+p2.ff, p1.ss+p2.ss};
}

vector<pr> m4 = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool isValid(pr p) {
    if (p.ff < 0 || p.ss < 0 || p.ff >= n || p.ss >= n || a[p.ff][p.ss] == 'T') return false;
    return true;
}



bool check(int tm) {
    queue<tuple<pr, ll>> q;
    memset(vis, 0, sizeof(vis));


    q.push({st, s*(tm+1)});
    bool f = false;

    vector<vi> k(n, vi(n));

    while (!q.empty()) {
        auto [e, i] = q.front(); q.pop();

        if (vis[e.ff][e.ss]) continue;
        vis[e.ff][e.ss] = true;
        k[e.ff][e.ss] = (i+s-1)/s;

        ll ni = i+1;

        for (auto d : m4) {
            pr m = d+e;

            if (vis[m.ff][m.ss] || !isValid(m) || ni/s > ti[m.ff][m.ss]) continue;

            q.push({m, ni});

        }


    }




    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << k[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;


    return vis[de.ff][de.ss];
}



int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> a[i];

    


    queue<pair<pr, ll>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'H')  {
                q.push({{i,j}, 0});
            }
            if (a[i][j] == 'M') {
                st = {i, j};
            }

            if (a[i][j] == 'D') {
                vis[i][j] = true;
                ti[i][j] = inf+10;
                de = {i, j};
            }


        }
    }
    while (!q.empty()) {
        auto [e, t] = q.front(); q.pop();

        if (vis[e.ff][e.ss]) continue;
        vis[e.ff][e.ss] = true;
        ti[e.ff][e.ss] = t;

        for (auto d : m4) {
            pr m = e+d;
            if (!isValid(m) || vis[m.ff][m.ss]) continue;
            q.push({m, t+1});
        }
    }




    ll i = -1, j = 650000;
    ll ans = -1;
    while (i <= j) {
        ll mid = (i + j)/2;
        if (check(mid)) {
            ans = mid;
            i = mid+1;
        } else {
            j = mid-1;
        }

    }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << ti[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;


    // cout << check(2) << endl;

    
    cout << ans << endl;



    return 0;
}

• Subtask 1: 84 / 100