Submission #1237848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237848		matisito	Mecho (IOI09_mecho)	C++20	22 / 100	127 ms	6216 KiB

mecho

#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";

/*  
MC lover
*/

const int maxN=800;
char lab[maxN+1][maxN+1];
int dis[maxN+1][maxN+1], vm[maxN+1][maxN+1];

int dirX[]={1, 0, -1, 0};
int dirY[]={0, 1, 0, -1};

void solve(){
    int n, s; cin>>n>>s;
    queue<pair<int, int>>mulbfs;
    auto in=[&](int x, int y){
        return x>=0 && y>=0 && x<n && y<n;
    };
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<n ; j++){
            dis[i][j]=1e9;
            cin>>lab[i][j];
            if(lab[i][j]=='H'){
                mulbfs.push({i, j});
                dis[i][j]=0;
                // dbg(i)
                // dbg(j)
            }
        }
    }
    int ans=-1;
    while(!mulbfs.empty()){
        pair<int, int>x=mulbfs.front();
        // cout<<x.first<<" "<<x.second<<"\n";
        mulbfs.pop();
        for(int k=0 ; k<4 ; k++){
            int xx=x.first+dirX[k], yy=x.second+dirY[k];
            if(!in(xx, yy)) continue;
            // dbg(xx)
            // dbg(yy)
            if(dis[xx][yy]==1e9 && lab[xx][yy]!='T'){
                dis[xx][yy]=dis[x.first][x.second]+1;
                mulbfs.push({xx, yy});
            }
        }
    }
    int l=1, r=(n+1)*(n+1);
    while(l<=r){
        int mid=(l+r)/2;
        // mid=2;
        pair<int, int>start, end;
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<n ; j++){
                vm[i][j]=1e9;
                // cout<<dis[i][j]<<" ";
                if(lab[i][j]=='M') start={i, j};
                if(lab[i][j]=='D') end={i, j};
            }
            // cout<<"\n";
        }
        // cout<<"\n";
        vm[start.first][start.second]=0;
        queue<pair<int, int>>bfs;
        bfs.push(start);
        while(!bfs.empty()){
            pair<int, int>x=bfs.front();
            bfs.pop();
            for(int k=0 ; k<4 ; k++){
                int xx=x.first+dirX[k], yy=x.second+dirY[k];
                if(!in(xx, yy)) continue;
                // dbg(xx)
                // dbg(yy)
                if(vm[xx][yy]==1e9 && lab[xx][yy]!='T' && dis[xx][yy]>=(((vm[x.first][x.second])+s)/s)+mid){
                    vm[xx][yy]=vm[x.first][x.second]+1;
                    bfs.push({xx, yy});
                }
            }
        }
        // for(int i=0 ; i<n ; i++){
        //     for(int j=0 ; j<n ; j++) cout<<vm[i][j]<<" ";
        //     cout<<"\n";
        // }
        // dbg(vm[end.first][end.second])
        if(vm[end.first][end.second]==1e9) r=mid-1;
        else{
            l=mid+1;
            ans=mid;
        }
        // break;
    }
    cout<<ans<<"\n";
}

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

• Subtask 1: 22 / 100