Submission #916972

#	Time	Username	Problem	Language	Result	Execution time	Memory
916972		vanea	Mecho (IOI09_mecho)	C++14	100 / 100	480 ms	7972 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 801;
int n, s;
vector<string> field(mxN);

int d1[mxN][mxN], d2[mxN][mxN];
bool vis1[mxN][mxN], vis2[mxN][mxN];

vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

void restart() {
    memset(vis1, false, sizeof vis1);
    memset(vis2, false, sizeof vis2);
    memset(d1, 0, sizeof d1);
    memset(d2, 0, sizeof d2);
}

bool valid(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n && (field[x][y] == 'G' ||
                                    field[x][y] == 'M'));
}

bool reached(int a, int b) {
    return a/s < b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    array<int, 2> start, finish;
    vector<array<int, 2>> hives;
    for(int i = 0; i < n; i++) {
        cin >> field[i];
        for(int j = 0; j < n; j++) {
            if(field[i][j] == 'M') start = {i, j};
            else if(field[i][j] == 'H') hives.push_back({i, j});
            else if(field[i][j] == 'D') finish = {i, j};
        }
    }
    int l = 0, r = n * n;
    bool imp = true;
    while(l <= r) {
        int mid = (r+l) / 2;
        restart();
        queue<array<int, 2>> q;
        for(auto it : hives) {
            q.push(it);
            vis1[it[0]][it[1]] = true;
        }
        while(!q.empty()) {
            int x = q.front()[0], y = q.front()[1];
            q.pop();
            for(int k = 0; k < 4; k++) {
                int a = x + dx[k], b = y + dy[k];
                if(valid(a, b) && !vis1[a][b]) {
                    vis1[a][b] = true;
                    d1[a][b] = d1[x][y]+1;
                    q.push({a, b});
                }
            }
        }
        q.push(start);
        vis2[start[0]][start[1]] = true;
        if(d1[start[0]][start[1]] <= mid) q.pop();
        while(!q.empty()) {
            int x = q.front()[0], y = q.front()[1];
            q.pop();
            for(int k = 0; k < 4; k++) {
                int a = x + dx[k], b = y + dy[k];
                if(valid(a, b) && !vis2[a][b] && reached(d2[x][y]+1,
                                                         d1[a][b]-mid)) {
                    vis2[a][b] = true;
                    q.push({a, b});
                    d2[a][b] = d2[x][y]+1;
                }
            }
        }
        bool can = false;
        for(int k = 0; k < 4; k++) {
            int a = finish[0]+dx[k], b = finish[1]+dy[k];
            if(valid(a, b) && reached(d2[a][b], d1[a][b]-mid) && vis2[a][b]) {
                can = true;
            }
        }
        if(can)
            l = mid+1;
        else
            r = mid-1;
    }
    cout << l-1;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:46:10: warning: unused variable 'imp' [-Wunused-variable]
   46 |     bool imp = true;
      |          ^~~
mecho.cpp:85:35: warning: 'finish.std::array<int, 2>::_M_elems[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |             int a = finish[0]+dx[k], b = finish[1]+dy[k];
      |                                   ^
mecho.cpp:85:56: warning: 'finish.std::array<int, 2>::_M_elems[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |             int a = finish[0]+dx[k], b = finish[1]+dy[k];
      |                                                        ^

• Subtask 1: 100 / 100