Submission #1275083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275083		lmduc270410	Mecho (IOI09_mecho)	C++20	20 / 100	1097 ms	26840 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 800 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

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

int n, k;
string a[N], b[N];

queue<pair<pii, int>> qu;
void ms_bfs(int t){

    while(!qu.empty()) qu.pop();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(b[i][j] == 'H') qu.push({{i, j}, t});
        }
    }
    while(!qu.empty()){
        pii ord = qu.front().fi;
        int x = ord.fi, y = ord.se, remain = qu.front().se;
        qu.pop();
        if(!remain) continue;
        for(int dir = 0; dir < 4; dir++){
            int u = x + dx[dir], v = y + dy[dir];
            if(u < 0 || u >= n || v < 0 || v >= n || b[u][v] != 'G') continue;
            b[u][v] = 'H'; qu.push({{u, v}, remain - 1});
        }
    }
}

vector<pii> mechoo(vector<pii> cur){

    vector<pii> tmp;
    while(!qu.empty()) qu.pop();
    for(pii ord : cur){
        int x = ord.fi, y = ord.se;
        if(b[x][y] == 'H') continue;
        qu.push({{x, y}, k});
    }
    while(!qu.empty()){
        pii ord = qu.front().fi;
        int x = ord.fi, y = ord.se, remain = qu.front().se;
        qu.pop();
        tmp.push_back({x, y});
        if(!remain){
            continue;
        }
        for(int dir = 0; dir < 4; dir++){
            int u = x + dx[dir], v = y + dy[dir];
            if(u < 0 || u >= n || v < 0 || v >= n) continue;
            if(b[u][v] != 'G' && b[u][v] != 'D') continue;
            b[u][v] = 'M'; qu.push({{u, v}, remain - 1});
        }
    }
    return tmp;
}

bool bfs(){
    
    vector<pii> be1, be2; //bees
    vector<pii> me; //mecho
    pii en = {-1, -1};
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(b[i][j] == 'M') me.push_back({i, j});
            if(b[i][j] == 'H') be1.push_back({i, j});
            if(b[i][j] == 'D') en = {i, j};
        }
    }
    // cout<<"\nMECHOOOO\n";
    // for(pii ord : me) cout<<ord.fi<<" "<<ord.se<<'\n';
    // cout<<"BEEEEEEEEEEEEEEEES\n";
    // for(pii ord : be1) cout<<ord.fi<<" "<<ord.se<<'\n';
    // cout<<"HOME "<<en.fi<<" "<<en.se<<'\n';
    // return;

    while(!me.empty()){
        me = mechoo(me);
        if(b[en.fi][en.se] == 'M') return 1;
        be2.clear();
        for(pii ord : be1){
            int x = ord.fi, y = ord.se;
            for(int dir = 0; dir < 4; dir++){
                int u = x + dx[dir], v = y + dy[dir];
                if(u < 0 || u >= n || v < 0 || v >= n) continue;
                if(b[u][v] != 'M' && b[u][v] != 'G') continue;
                b[u][v] = 'H'; be2.push_back({u, v});
            }
        }
        be1.clear(); swap(be1, be2);
        // cout<<"----------------------\n";
        // for(int i = 0; i < n; i++) cout<<b[i]<<'\n';
    }
    return 0;
}

bool check(int t){

    for(int i = 0; i < n; i++) b[i] = a[i];
    ms_bfs(t);
    // for(int i = 0; i < n; i++) cout<<b[i]<<'\n';
    return bfs();
}

void solve(){
    
    cin>>n>>k;
    for(int i = 0; i < n; i++) cin>>a[i];

    // cout<<check(1); return;
    int l = 0, r = 2 * n, mid;
    while(l <= r){
        mid = (l + r) >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout<<r;
}

signed main(){
    
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin>>tc;
    while(tc--) solve();
}

• Subtask 1: 20 / 100