제출 #1275094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275094		lmduc270410	Mecho (IOI09_mecho)	C++20	46 / 100	1097 ms	24860 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];

void ms_bfs(int t){
    queue<pair<pii, int>> qu;
    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().first;
        int x = ord.first, y = ord.second, remain = qu.front().second;
        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) continue;
            // cho ong lan vao G HOAC M (M la o bat dau cua Me)
            if(b[u][v] != 'G' && b[u][v] != 'M') continue;
            b[u][v] = 'H'; qu.push({{u, v}, remain - 1});
        }
    }
}

vector<pii> mechoo(vector<pii> cur){
    vector<pii> tmp;
    queue<pair<pii, int>> qu;
    for(pii ord : cur){
        int x = ord.first, y = ord.second;
        if(b[x][y] == 'H') continue;
        qu.push({{x, y}, k});
    }
    while(!qu.empty()){
        pii ord = qu.front().first;
        int x = ord.first, y = ord.second, remain = qu.front().second;
        qu.pop();
        // ô này reachable trong <=k bước -> có thể đứng ở đây cuối phút
        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' && b[u][v] != 'M') continue;
            if(b[u][v] == 'H') continue; // ko di vao ong
            // dấu visited để khỏi push lại cùng ô nhiều lần trong cùng phút
            if(b[u][v] == 'M') continue; // đã đánh dấu
            // ta cần đánh dấu để tránh push trùng (chỉ trong mô phỏng này)
            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};
        }
    }
    if(en.first == -1) return false;

    while(!me.empty()){
        me = mechoo(me);
        if(b[en.fi][en.se] == 'M') return true;
        be2.clear();
        for(pii ord : be1){
            int x = ord.first, y = ord.second;
            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' && b[u][v] != 'D') continue;
                // ong ko vao D? theo de bai ong ko vao D, neu D la duong ve, khong cho D.
                if(b[u][v] == 'D') continue;
                if(b[u][v] == 'H') continue;
                b[u][v] = 'H'; be2.push_back({u, v});
            }
        }
        be1.clear(); swap(be1, be2);
    }
    return false;
}

bool check(int t){
    for(int i = 0; i < n; i++) b[i] = a[i];
    ms_bfs(t);
    return bfs();
}

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

    int l = 0, r = n * n, mid; // <-- để r = n*n thay vì 2*n
    int ans = -1;
    while(l <= r){
        mid = (l + r) >> 1;
        if(check(mid)){ ans = mid; l = mid + 1; }
        else r = mid - 1;
    }
    cout<<ans<<"\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 46 / 100