Submission #1073905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073905		gavangno01	Mecho (IOI09_mecho)	C++17	79 / 100	149 ms	8944 KiB

mecho

#include<bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

const int dx[] = {1, 0, 0, -1};
const int dy[] = {0, 1, -1, 0};
const int MAXN = 8e2 + 10;
const int inf = 1e9 + 7;
int n, s;
int xe, ye;
int grid[MAXN][MAXN];
int loangbee[MAXN][MAXN];
int loangpl[MAXN][MAXN];

bool exceed(int x, int y) {
    return (x > n || x < 1 || y > n || y < 1);
}
void bfsbee() {
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == 4) {
                q.push({i, j});
                loangbee[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        pii temp = q.front();
        q.pop();
        int x = temp.fi;
        int y = temp.se;
        for (int i = 0; i < 4; i++) {
            int u = x + dx[i];
            int v = y + dy[i];
            if (!exceed(u, v)) {
                if (loangbee[u][v] == inf && grid[u][v] == 1) {
                    loangbee[u][v] = loangbee[x][y] + 1;
                    q.push({u, v});
                }
            }
        }
    }
}
int bfspl(int original_value) {
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == 2) {
                q.push({i, j});
                loangpl[i][j] = 0;
            }
            else {
                loangpl[i][j] = inf;
            }
        }
    }
    while (!q.empty()) {
        pii temp = q.front();
        q.pop();
        int x = temp.fi;
        int y = temp.se;
        int time = loangpl[x][y] / s;
        //if (loangpl[x][y] % s != 0) time++;
        time += original_value;
        if (time >= loangbee[x][y]) {
            loangpl[x][y] = -1;
            continue;
        }
        for (int i = 0; i < 4; i++) {
            int u = x + dx[i];
            int v = y + dy[i];
            if (!exceed(u, v)) {
                if (loangpl[u][v] == inf && grid[u][v] == 1) {
                    if ((loangpl[x][y] + 1) / s < loangbee[u][v]) {
                        q.push({u, v});
                        loangpl[u][v] = loangpl[x][y] + 1;
                    };
                }
            }
        }
    }
    if (loangpl[xe][ye] == inf) return 0;
    int timedi = loangpl[xe][ye] / s;
    return timedi < loangbee[xe][ye] - original_value;
}

int main() {
    cin >> n >> s;

    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        for (int j = 1; j <= n; j++) {
            char c = str[j-1];
            loangpl[i][j] = inf;
            loangbee[i][j] = inf;
            if (c == 'T') {
                grid[i][j] = 0;
            }
            if (c == 'G') grid[i][j] = 1;
            if (c == 'M') grid[i][j] = 2;
            if (c == 'D') {
                grid[i][j] = 1;
                xe = i;
                ye = j;
            }
            if (c == 'H') grid[i][j] = 4;
        }
    }
    bfsbee();
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= n; j++) {
//            cout << loangbee[i][j] << " ";
//        }
//        cout << endl;
//    }
//    cout << "map nguoi" << endl;
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= n; j++) {
//            cout << loangpl[i][j] << " ";
//        }
//        cout << endl;
//
    int l = 0, r = n * n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (bfspl(mid) == 1) {
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << l - 1;
    return 0;
}

• Subtask 1: 79 / 100