Submission #470710

#	Time	Username	Problem	Language	Result	Execution time	Memory
470710		dooompy	Mecho (IOI09_mecho)	C++17	84 / 100	218 ms	5572 KiB

mecho

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

bool tree[1005][1005];
int bees[1005][1005];
bool seen[1005][1005];
int n, s, sx, sy, dx, dy;

int mx[]{1, -1, 0, 0};
int my[]{0, 0, 1, -1};

struct bear {
    int x, y, time, move;
};

bool able(int time) {
    fill(&seen[0][0], &seen[0][0] + sizeof(seen) / sizeof(seen[0][0]), false);
    int curtime = time;

    // curtime can go into curtime+2 but must finish on curtime+3

    queue<bear> q;
    q.push({sx, sy, curtime+2, 0});
//    seen[sx][sy] = true;

    if (bees[sx][sy] < curtime + 2) return false;

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

        if (seen[cur.x][cur.y]) continue;

        if (cur.move == s) {
            cur.time++;
            if (bees[cur.x][cur.y] < cur.time) {
                continue;
            }
            cur.move = 0;
        }

        if (cur.x == dx && cur.y == dy) return true;


        seen[cur.x][cur.y] = true;

        for (int i = 0; i < 4; i++) {
            int newx = cur.x + mx[i], newy = cur.y + my[i];

            if (newx < 0 || newx >= n || newy < 0 || newy >= n || bees[newx][newy] < cur.time || tree[newx][newy] || seen[newx][newy]) continue;

            q.push({newx, newy, cur.time, cur.move+1});
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    cin >> n >> s;
    queue<pair<int, int>> q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char c; cin>> c;
            if (c == 'T') tree[i][j] = true;
            if (c == 'M') {
                sx = i; sy = j;

            }
            if (c == 'D') {
                dx = i; dy = j;
            }
            if (c == 'H') {
                q.push({i, j});
                bees[i][j] = 1;
            }
        }
    }

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

        for (int i = 0; i < 4; i++) {
            int newx = cur.first + mx[i], newy = cur.second + my[i];
            if (newx < 0 || newx >= n || newy < 0 || newy >= n || bees[newx][newy] || tree[newx][newy]) continue;
            bees[newx][newy] = bees[cur.first][cur.second] + 1;
            q.push({newx, newy});
        }
    }

    int lo = 0, hi = 1e9;

    int biggest = -1;

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (able(mid)) {
            biggest = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    cout << biggest;

}

• Subtask 1: 84 / 100