Submission #196190

#	Time	Username	Problem	Language	Result	Execution time	Memory
196190		tri	Mecho (IOI09_mecho)	C++14	100 / 100	290 ms	7672 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int MAXN = 1000;
const int INF = 1e9;

int unuse[MAXN][MAXN];
int reach[MAXN][MAXN];

const int dI[] = {-1, 0, 1, 0};
const int dJ[] = {0, -1, 0, 1};

int N, S;
pi st, goal;

bool reachGoal(int delay) {
    if (delay == -1) return true;
    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
            reach[i][j] = INF;
        }
    }

    reach[st.f][st.s] = delay * S;
    queue<pi> q;
    q.push(st);

    while (q.size()) {
        pi cur = q.front();
        q.pop();

        if (reach[cur.f][cur.s] < unuse[cur.f][cur.s] * S) {
            for (int d = 0; d < 4; d++) {
                int nI = cur.f + dI[d];
                int nJ = cur.s + dJ[d];

                if (reach[nI][nJ] == INF) {
                    reach[nI][nJ] = reach[cur.f][cur.s] + 1;
                    q.push({nI, nJ});
                }
            }
        }
    }

    return reach[goal.f][goal.s] != INF;
}

int binSearch() {
    int low = -1;
    int high = 800 * 800;

    while (low != high) {
        int mid = (low + high + 1) / 2;

        if (reachGoal(mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

int main() {
    cin >> N >> S;

    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
            unuse[i][j] = -1;
        }
    }

    for (int i = 0; i <= N + 1; i++) {
        unuse[0][i] = 0;
        unuse[N + 1][i] = 0;
        unuse[i][0] = 0;
        unuse[i][N + 1] = 0;
    }

    queue<pi> q;
    for (int i = 1; i <= N; i++) {
        string line;
        cin >> line;
        for (int j = 1; j <= N; j++) {
            char cur = line[j - 1];
            if (cur == 'T') {
                unuse[i][j] = 0;
            } else if (cur == 'H') {
                unuse[i][j] = 0;
                q.push({i, j});
            } else if (cur == 'M') {
                st = {i, j};
            } else if (cur == 'D') {
                goal = {i, j};
                unuse[i][j] = INF;
            } else {
                assert(cur == 'G');
            }
        }
    }

    while (!q.empty()) {
        pi cur = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nI = cur.f + dI[d];
            int nJ = cur.s + dJ[d];
            if (unuse[nI][nJ] == -1) {
                unuse[nI][nJ] = unuse[cur.f][cur.s] + 1;
                q.push({nI, nJ});
            }
        }
    }
    int ans = binSearch();
    cout << ans << endl;
}

• Subtask 1: 100 / 100