Submission #679600

#	Time	Username	Problem	Language	Result	Execution time	Memory
679600		omikron123	Mecho (IOI09_mecho)	C++14	73 / 100	271 ms	7536 KiB

mecho

// https://oj.uz/problem/view/IOI09_mecho

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

// binary search + BFS

// n <= 800, s <= 1000
int n, s;
char m[805][805];
int mr,mc,dr,dc;
struct E {
    int r,c,d;
};
queue<E> q;
const int INF = 1e9;
int beetime[805][805];    // time for bees to reach here
int steps[805][805];    // min steps for mecho to reach here

// init q before calling this
void bfs() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            beetime[i][j] = -1;
    while (!q.empty()) {
        E e = q.front();
        q.pop();
        if (e.r < 0 || e.r >= n || e.c < 0 || e.c >= n) continue;
        if (m[e.r][e.c] == 'T' || m[e.r][e.c] == 'D' || beetime[e.r][e.c] != -1) continue;
        beetime[e.r][e.c] = e.d;
        q.push({e.r+1, e.c, e.d+1});
        q.push({e.r-1, e.c, e.d+1});
        q.push({e.r, e.c+1, e.d+1});
        q.push({e.r, e.c-1, e.d+1});
    }
}

// check if eating honey for t minutes is ok
bool check(int t) {
    q.push({mr, mc, t*s});
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            steps[i][j] = -1;
    while (!q.empty()) {
        E e = q.front();
        q.pop();
        if (e.r < 0 || e.r >= n || e.c < 0 || e.c >= n) continue;
        if (m[e.r][e.c] == 'T' || steps[e.r][e.c] != -1) continue;
        if (beetime[e.r][e.c] != -1 && e.d / s >= beetime[e.r][e.c]) continue; // stinged by bees
        steps[e.r][e.c] = e.d;
        q.push({e.r+1, e.c, e.d+1});
        q.push({e.r-1, e.c, e.d+1});
        q.push({e.r, e.c+1, e.d+1});
        q.push({e.r, e.c-1, e.d+1});
    }
    return steps[dr][dc] != -1;
}

int main() {
    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++) {
        scanf("%s", m[i]);
        for (int j = 0; j < n; j++)
            if (m[i][j] == 'M') mr = i, mc = j;
            else if (m[i][j] == 'D') dr = i, dc = j;
            else if (m[i][j] == 'H') q.push({i,j,0});
    }

    bfs();      // calc beetime[][]

    int lo = 0, hi = 2000;
    while (lo < hi) {
        int mid = (lo+hi+1) / 2;
        if (check(mid))
            lo = mid;
        else
            hi = mid-1;
    }
    if (lo == 0 && !check(0))
        printf("-1");
    else
        printf("%d", lo);

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d", &n, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%s", m[i]);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 73 / 100