Submission #969052

#	Time	Username	Problem	Language	Result	Execution time	Memory
969052		Boomyday	Mecho (IOI09_mecho)	C++17	84 / 100	631 ms	6272 KiB

mecho

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

#define f first
#define s second

using ii = pair<int,int>;
int N, S;

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

bool in_bounds(pair<int,int> p){
    return 0 <= p.f && p.f < N && 0 <= p.s && p.s < N;
}



queue<ii> push_bees(vector<vector<int>>& G, queue<ii> Q){

    queue<ii> Q2;
    while (!Q.empty()){
        ii cur = Q.front(); Q.pop();
        for (int d=0;d<4;++d){
            ii nxt = {cur.f+dx[d],cur.s+dy[d]};
            if (!in_bounds(nxt)) continue;
            if (G[nxt.f][nxt.s] == 0 || (G[nxt.f][nxt.s] == 2 && nxt != p_en)){
                G[nxt.f][nxt.s] = -1;
                Q2.push(nxt);
            }
        }
    }
    return Q2;
}

queue<ii> push_mecho(vector<vector<int>>& G, queue<ii> Q){

    queue<ii> Q2;
    while (!Q.empty()){
        ii cur = Q.front(); Q.pop();
        if (G[cur.f][cur.s] != 2) continue;
        for (int d=0;d<4;++d){
            ii nxt = {cur.f+dx[d],cur.s+dy[d]};
            if (!in_bounds(nxt)) continue;
            if (G[nxt.f][nxt.s] == 0){
                G[nxt.f][nxt.s] = 2;
                Q2.push(nxt);
            }
        }
    }
    return Q2;
}
bool good(int t, vector<vector<int>> G){
    queue<ii> Q; // bees
    for(int i=0;i<N;++i) for(int j=0;j<N;++j) if (G[i][j] == -1) Q.push({i,j});

    for(int i=0;i<t;++i) Q = push_bees(G,Q);
    queue<ii> Q2; Q2.push(p_st); // mecho

    while(!Q2.empty()){

        for (int i=0;i<S;++i) Q2 = push_mecho(G,Q2);
        Q = push_bees(G,Q);
    }

    return G[p_en.f][p_en.s] == 2;

}

int main(){
    cin >> N >> S;
    vector<vector<int>> G(N,vector<int>(N,0));

    for(int i=0;i<N;++i){
        string st;
        cin >> st;
        for(int j=0;j<N;++j){
            if (st[j]=='T'){
                G[i][j] = 1;
            }
            if (st[j] == 'G'){
                G[i][j] = 0;
            }
            if (st[j] == 'M'){
                p_st = {i,j};
                G[i][j] = 2;
            }
            if (st[j] == 'D'){
                p_en = {i,j};
                G[i][j] = 0;
            }
            if (st[j] == 'H'){
                G[i][j] = -1;
            }
        }
    }


    if (!good(0,G)){
        cout << -1 << endl; return 0;
    }


    int lo = 0, hi = 1e6;
    while (lo < hi){

        int mid = (lo+hi+1)/2;

        if (good(mid,G)){
            lo = mid;
        }
        else {
            hi = mid-1;
        }
    }
    cout << lo << endl;
}

• Subtask 1: 84 / 100