Submission #973047

#	Time	Username	Problem	Language	Result	Execution time	Memory
973047		njoop	Mecho (IOI09_mecho)	C++14	21 / 100	288 ms	10580 KiB

mecho

#include <bits/stdc++.h>
#define pi pair<int, int>
#define ti tuple<int, int, int>
#define tii tuple<int, int, int, int>
using namespace std;

int n, s, bee[810][810], stx, sty, enx, eny, cx, cy, cs, cdi, l=0, r=1e9, mid;
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
pi mec[810][810];
vector<pi> hi;
char arr[810][810];

bool solve(int mn) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            mec[i][j] = {1e9, 1e9};
        }
    }
    queue<tii> q;
    q.push({stx, sty, 0, 0});
    while(q.size()) {
        cx = get<0>(q.front());
        cy = get<1>(q.front());
        cdi = get<2>(q.front());
        cs = get<3>(q.front());
        q.pop();
        if(cs == s) {
            cs = 0;
            cdi++;
        }
        if(cx < 1 || cx > n || cy < 1 || cy > n || arr[cx][cy] == 'T' || mec[cx][cy].first <= cdi) continue;
        if(mec[cx][cy].first == cdi && mec[cx][cy].second <= cs) continue;
        if(cdi+mn+(cs ? 1 : 0) >= bee[cx][cy]) continue;
        mec[cx][cy] = {cdi, cs};
        for(int i=0; i<4; i++) {
            q.push({cx+di[i], cy+dj[i], cdi, cs+1});
        }
    }
    return mec[enx][eny].first != 1e9;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            bee[i][j] = 1e9;
            cin >> arr[i][j];
            if(arr[i][j] == 'M') {
                stx = i;
                sty = j;
            } else if(arr[i][j] == 'D') {
                enx = i;
                eny = j;
            } else if(arr[i][j] == 'H') {
                hi.push_back({i, j});
            }
        }
    }
    queue<ti> q;
    for(auto i: hi) {
        q.push({i.first, i.second, 0});
    }
    while(q.size()) {
        cx = get<0>(q.front());
        cy = get<1>(q.front());
        cdi = get<2>(q.front());
        q.pop();
        if(cx < 1 || cx > n || cy < 1 || cy > n || arr[cx][cy] == 'T' || bee[cx][cy] <= cdi) continue;
        bee[cx][cy] = cdi;
        for(int i=0; i<4; i++) {
            q.push({cx+di[i], cy+dj[i], cdi+1});
        }
    }
    while(l < r) {
        mid = (l+r)>>1;
        if(solve(mid)) {
            l = mid+1;
        } else {
            r = mid;
        }
    }
    cout << l;
    return 0;
}

• Subtask 1: 21 / 100