Submission #489345

#	Time	Username	Problem	Language	Result	Execution time	Memory
489345		Alexandruabcde	Mecho (IOI09_mecho)	C++14	47 / 100	193 ms	6696 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 805;
typedef pair <int, int> PII;

int N, S;
char init[NMAX][NMAX];
int viz[NMAX][NMAX];

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

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> S;

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= N; ++ j )
            cin >> init[i][j];
}

bool Interior (int x, int y) {
    return 0 < x && x < N+1 && 0 < y && y < N+1;
}

void Expand (queue <PII> &Bees) {
    queue <PII> next;

    while (!Bees.empty()) {
        PII P = Bees.front();
        Bees.pop();

        for (int i = 0; i < 4; ++ i ) {
            PII urm = {P.first + dx[i], P.second + dy[i]};

            if (Interior(urm.first, urm.second) && (init[urm.first][urm.second] == 'G' || init[urm.first][urm.second] == 'M') && viz[urm.first][urm.second] != -1) {
                next.push(urm);
                viz[urm.first][urm.second] = -1;
            }
        }
    }

    Bees = next;
}

bool Check (int wait) {
    queue <PII> Ends, CanExp;
    PII finish;

    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= N; ++ j ) {
            if (init[i][j] == 'T') viz[i][j] = -1;

            if (init[i][j] == 'G') viz[i][j] = 0;

            if (init[i][j] == 'M') {
                Ends.push({i, j});
                viz[i][j] = 1;
            }

            if (init[i][j] == 'D') {
                finish = {i, j};
                viz[i][j] = 0;
            }

            if (init[i][j] == 'H') {
                CanExp.push({i, j});
                viz[i][j] = -1;
            }
        }
    }

    for (int i = 1; i <= wait; ++ i )
        Expand(CanExp);

    bool finished = 0;
    while (!finished && !Ends.empty()) {
        for (int pas = 1; pas <= S; ++ pas ) {
            queue <PII> nextEnds;
            while (!Ends.empty()) {
                PII P = Ends.front();
                Ends.pop();

                if (viz[P.first][P.second] != 1) continue;

                for (int i = 0; i < 4; ++ i ) {
                    PII urm = {P.first + dx[i], P.second + dy[i]};

                    if (Interior(urm.first, urm.second) && viz[urm.first][urm.second] == 0) {
                        nextEnds.push(urm);
                        viz[urm.first][urm.second] = 1;
                    }
                }
            }

            Ends = nextEnds;
        }

        if (viz[finish.first][finish.second]) finished = 1;
        Expand(CanExp);
    }

    return finished;
}

int aux[NMAX][NMAX];
int FindRight () {
    queue <PII> Q;
    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= N; ++ j ) {
            aux[i][j] = 0;

            if (init[i][j] == 'H') {
                Q.push({i, j});
                aux[i][j] = 1;
            }
        }

    while (!Q.empty()) {
        PII x = Q.front();
        Q.pop();

        for (int i = 0; i < 4; ++ i ) {
            PII urm = {x.first + dx[i], x.second + dy[i]};

            if (Interior(urm.first, urm.second) && aux[urm.first][urm.second] == 0){
                aux[urm.first][urm.second] = aux[x.first][x.second]+1;
                Q.push(urm);
            }
        }
    }

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= N; ++ j )
            if (init[i][j] == 'M') return (aux[i][j] == 0 ? N*N : aux[i][j]);
}

void Solve () {
    int st = 0, dr = FindRight();
    int ans = -1;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (Check(mij)) {
            ans = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    cout << ans << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int FindRight()':
mecho.cpp:112:17: warning: control reaches end of non-void function [-Wreturn-type]
  112 |     queue <PII> Q;
      |                 ^

• Subtask 1: 47 / 100