Submission #499625

#	Time	Username	Problem	Language	Result	Execution time	Memory
499625		rampu	Mecho (IOI09_mecho)	C++14	84 / 100	242 ms	6128 KiB

mecho

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#define F first
#define S second
using namespace std;

using pii = pair <int, int>;

const int N = 801;
const int dx[] = { 0, -1, 1, 0 };
const int dy[] = { 1, 0, 0, -1 };

int n, s;
char c[N][N];

int tAcc[N][N];
vector <pii> hive;
pii honeypot, home;

inline bool Unreachable(const int &x, const int &y) {
    return x < 1 || x > n || y < 1 || y > n || c[x][y] == 'D' || c[x][y] == 'T';
}

inline bool UnrB(const int &x, const int &y) {
    return x < 1 || x > n || y < 1 || y > n || c[x][y] == 'T';
}

void CalcTAcc() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) tAcc[i][j] = INT_MAX;

    queue <pii> q;
    for (auto p: hive) q.push(p), tAcc[p.F][p.S] = -1;
    while (q.size()) {
        int ux = q.front().F;
        int uy = q.front().S;
        q.pop();

        for (int d = 0; d < 4; d++) {
            int vx = ux + dx[d];
            int vy = uy + dy[d];

            if (Unreachable(vx, vy) || tAcc[vx][vy] != INT_MAX) continue;
            tAcc[vx][vy] = tAcc[ux][uy] + 1;
            q.push({ vx, vy });
        }
    }
}

bool isFine(int t) {
    vector <vector <int> > step(n + 1);
    for (auto &v: step) v.resize(n + 1, INT_MAX);

    queue <pii> q;
    q.push(honeypot), step[honeypot.F][honeypot.S] = 0;
    while (q.size()) {
        int ux = q.front().F;
        int uy = q.front().S;
        q.pop();

        for (int d = 0; d < 4; d++) {
            int vx = ux + dx[d];
            int vy = uy + dy[d];

            if (UnrB(vx, vy) || step[vx][vy] != INT_MAX) continue;

            step[vx][vy] = step[ux][uy] + 1;
            if (t + step[vx][vy] / s > tAcc[vx][vy]) continue;

            if (c[vx][vy] == 'D') return true;
            q.push({ vx, vy });
        }
    }
    return false;
}

int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> c[i][j];
            if (c[i][j] == 'H') hive.push_back({ i, j });
            else if (c[i][j] == 'M') honeypot = { i, j };
            else if (c[i][j] == 'D') home = { i, j };
        }

    CalcTAcc();

    int l = 0, r = n * n, mid, out = -1;
    while (l <= r) {
        mid = l + (r - l >> 1);
        if (isFine(mid)) out = mid, l = mid + 1;
        else r = mid - 1;
    }

    cout << out;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:93:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   93 |         mid = l + (r - l >> 1);
      |                    ~~^~~

• Subtask 1: 84 / 100