제출 #1306856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306856		samarthkulkarni	Mecho (IOI09_mecho)	C++20	6 / 100	44 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 = 650000;
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 flag = false;

    vector<vi> temp(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;
        temp[e.ff][e.ss] = j;

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

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

            if (!isValid(m) || ti[m.ff][m.ss] < nj || vis[m.ff][m.ss]) continue;
            if (m == de) return true;
            q.push({m, ni, nj});
        }

    }

    return false;
}



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') {
                ti[i][j] = inf;
                st = {i, j};
            }

            if (a[i][j] == 'D') {
                vis[i][j] = true;
                ti[i][j] = inf;
                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 = 0;
    while (i <= j) {
        ll mid = (i + j)/2;
        if (check(mid)) {
            ans = mid;
            i = mid+1;
        } else {
            j = mid-1;
        }

    }

    cout << ans << endl;



    return 0;
}

• Subtask 1: 6 / 100