Submission #1019496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019496		lucascgar	Mecho (IOI09_mecho)	C++17	100 / 100	118 ms	7068 KiB

mecho

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
precalcula p grid o tempo que cada célula leva até ser ocupada por abelhas
binary search no tempo
p verificar se tempo x é válido:
floodfill do mecho começando no tempo x e ignorando s:
    continuar só se (dist[i][j]+s-1)/s + x < bee[i][j] ou se (dist[i][j]+s-1)/s + x == bee[i][j] e se nn for o último movimento, = dist[i][j]%s != 0
*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 800+10;

bool g[MAXN][MAXN];
int bs[MAXN][MAXN]; // bs=bees

int d[MAXN][MAXN]; // distance (mecho)
int aux[4] = {1, -1, 0, 0};
signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, s;
    cin >> n >> s;
    char x;
    pii st = {0,0}, en = {0,0};
    queue<pii> bq;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){
        cin >> x;
        g[i][j] = (x=='G' || x=='M');
        bs[i][j] = 1e9;

        if (x=='H'){
            bq.emplace(i,j);
            bs[i][j] = 0;
        }
        else if (x =='M') st = {i,j};
        else if (x == 'D') en = {i, j};


    }

    while (!bq.empty()){
        pii u = bq.front();
        bq.pop();

        int nd = bs[u.first][u.second]+1;

        for (int a=0,b=3;a<4;a++,b--){
            int ni = u.first+aux[a], nj = u.second+aux[b];

            if (bs[ni][nj] == 1e9 && g[ni][nj]){
                bs[ni][nj] = nd;
                bq.emplace(ni, nj);
            }

        }

    }

    g[en.first][en.second] = g[st.first][st.second] = 1;
    bool tru = 0;
    int in = 0, fi = 1e9, me;
    while (in<=fi){
        me = (in+fi)/2;

        if (bs[st.first][st.second] <= me){
            fi = me-1;
            continue;
        }

        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j] = 1e9;
        d[st.first][st.second] = 0;
        queue<pii> mq;
        mq.push(st);

        while (!mq.empty()){
            pii u = mq.front();
            mq.pop();
            int nd = d[u.first][u.second]+1;

            for (int a=0,b=3;a<4;a++,b--){
                int ni = u.first+aux[a], nj = u.second+aux[b];
                if (!g[ni][nj] || d[ni][nj] != 1e9) continue;

                if (me + (nd+s-1)/s < bs[ni][nj] || (me + (nd+s-1)/s == bs[ni][nj] && nd%s != 0)){
                    d[ni][nj] = nd;
                    mq.emplace(ni, nj);
                }

            }
        }

        if (d[en.first][en.second] != 1e9){
            tru=1, in = me+1;
        }else fi = me-1;

    }



    if (!tru) cout << "-1\n";

    else cout << in-1 << "\n"; 


    return 0;
}

• Subtask 1: 100 / 100