Submission #1194108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194108		anastasiskolio	Mecho (IOI09_mecho)	C++20	20 / 100	76 ms	6216 KiB

mecho

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define MAXN 800
#define INF 1000000

using namespace std;

int N, S;
int Si, Sj, Ti, Tj;

vector<vector<char>> A(MAXN, vector<char>(MAXN));
vector<vector<int>> Db(MAXN, vector<int>(MAXN));  // time bees arrive
vector<vector<int>> Dm(MAXN, vector<int>(MAXN));  // time Mecho arrives

queue<pair<int, int>> Qb;
queue<array<int, 3>> Qm;  // i, j, scent left

void BeesGoTo(int i, int j, int D) {
    if (i >= 0 && i < N && j >= 0 && j < N && A[i][j] != 'T' && A[i][j] != 'D' && Db[i][j] == INF) {
        Db[i][j] = D + 1;
        Qb.push({ i, j });
    }
}

void BeesBreadthFirstSearch() {
    while (!Qb.empty()) {
        int i = Qb.front().first;
        int j = Qb.front().second;
        Qb.pop();
        BeesGoTo(i + 1, j, Db[i][j]);
        BeesGoTo(i - 1, j, Db[i][j]);
        BeesGoTo(i, j + 1, Db[i][j]);
        BeesGoTo(i, j - 1, Db[i][j]);
    }
}

void MechoGoTo(int i, int j, int s, int D) {
    if (i < 0 || i >= N || j < 0 || j >= N) return;
    if (A[i][j] == 'T' || A[i][j] == 'H') return;
    if (Dm[i][j] != INF) return;

    int new_time = D + 1;
    if (new_time < Db[i][j]) {
        Dm[i][j] = new_time;
        int new_scent = (s > 0) ? s - 1 : S;
        Qm.push({ i, j, new_scent });
    }
}

bool MechoBreadthFirstSearch(int start_time) {
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            Dm[i][j] = INF;

    Qm = queue<array<int, 3>>();
    Dm[Si][Sj] = start_time;
    Qm.push({ Si, Sj, S });

    while (!Qm.empty()) {
        int i = Qm.front()[0];
        int j = Qm.front()[1];
        int s = Qm.front()[2];
        Qm.pop();

        MechoGoTo(i + 1, j, s, Dm[i][j]);
        MechoGoTo(i - 1, j, s, Dm[i][j]);
        MechoGoTo(i, j + 1, s, Dm[i][j]);
        MechoGoTo(i, j - 1, s, Dm[i][j]);
    }

    return Dm[Ti][Tj] != INF;
}

int main() {
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            Db[i][j] = INF;
            scanf(" %c", &A[i][j]);
            if (A[i][j] == 'H') {
                Db[i][j] = 0;
                Qb.push({ i, j });
            } else if (A[i][j] == 'M') {
                Si = i;
                Sj = j;
            } else if (A[i][j] == 'D') {
                Ti = i;
                Tj = j;
            }
        }
    }

    BeesBreadthFirstSearch();

    int lo = 0, hi = N * N;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (MechoBreadthFirstSearch(mid))
            lo = mid;
        else
            hi = mid - 1;
    }

    printf("%d\n", lo);
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d", &N, &S);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |             scanf(" %c", &A[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100