Submission #443322

#	Time	Username	Problem	Language	Result	Execution time	Memory
443322		MohammadAghil	Mecho (IOI09_mecho)	C++14	84 / 100	189 ms	4380 KiB

mecho

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 
 
const ll mod = 998244353, maxn = 800 + 5, inf = 1e9 + 5;

struct node{
    int x, y, rem, eq;
    node(){}
    node(int x, int y, int r, int e):
        x(x), y(y), rem(r), eq(e){}
};

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool bad[maxn][maxn], vis[maxn][maxn];
int dist_bee[maxn][maxn];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, s; cin >> n >> s;
    pair<int, int> st, en;
    deque<pair<int, int>> hol;  
    rep(i,0,n){
        rep(j,0,n){
            dist_bee[i][j] = inf;
            char e; cin >> e;
            if(e == 'M'){
                st = {i, j};
            }
            if(e == 'D'){
                en = {i, j};
            }
            if(e == 'H'){
                hol.push_back({i, j});
                dist_bee[i][j] = 0;
            }
            if(e == 'H' || e == 'T') bad[i][j] = 1;
        }
    }
    
    while(sz(hol)){
        pair<int, int> p = hol.front(); hol.pop_front();
        rep(d,0,4){
            int i = p.ff + dx[d], j = p.ss + dy[d];
            if(i < 0 || i >= n || j < 0 || j >= n || dist_bee[i][j] != inf || bad[i][j]) continue;
            dist_bee[i][j] = dist_bee[p.ff][p.ss] + 1;
            hol.pb({i, j});
        }
    }
    dist_bee[en.ff][en.ss] = inf;
    // rep(i,0,n){
    //     rep(j,0,n){
    //         if(dist_bee[i][j] == inf) cout << -1 << ' ';
    //         else cout << dist_bee[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    auto chk = [&](int t) -> bool{
        memset(vis, 0, sizeof vis);
        deque<node> q[2];
        bool act = 0;
        q[act].push_back(node(st.ff, st.ss, s, t + 1));
        vis[st.ff][st.ss] = 1;
        while(1){
            if(!sz(q[act])){
                act ^= 1;
            }
            if(!sz(q[act])) break;
            node p = q[act].front(); q[act].pop_front();
            rep(d,0,4){
                int i = p.x + dx[d], j = p.y + dy[d];
                if(i < 0 || i >= n || j < 0 || j >= n || vis[i][j] || bad[i][j] 
                    || p.eq > dist_bee[i][j] || (p.rem == 1 && p.eq == dist_bee[i][j])) continue;
                node r = node(i, j, p.rem - 1, p.eq);
                vis[i][j] = 1;
                if(!r.rem){
                    r.rem = s, r.eq++;
                    q[!act].pb(r);
                }else{
                    q[act].pb(r);
                }
            }
        }
        return vis[en.ff][en.ss];
    };
    int l = -1, r = 1e6;
    while(l + 1 < r){
        int mid = (l + r)/2;
        if(chk(mid)) l = mid;
        else r = mid;
    }
    cout << l;
    return 0;
}

• Subtask 1: 84 / 100