제출 #1306912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306912		samarthkulkarni	Mecho (IOI09_mecho)	C++20	19 / 100	166 ms	6928 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[800];
ll ti[800][800];
bool vis[800][800];
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, ll>> q;
    memset(vis, 0, sizeof(vis));


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

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

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



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

        k[e.ff][e.ss] = (j >= ti[e.ff][e.ss] ? inf : j);


        ll ni = (i == s ? 1 : i+1);
        ll nj = (i == s ? j+1 : j); 

        if (k[e.ff][e.ss] == inf && i == s) continue;



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

            if (!isValid(m) || vis[m.ff][m.ss]) continue;
            
            q.push({m, ni, nj});
        }

    }


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


    return k[de.ff][de.ss] > 0 && k[de.ff][de.ss] != inf;
}



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: 19 / 100