Submission #1288971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288971		abhi_atg	Mecho (IOI09_mecho)	C++20	100 / 100	143 ms	12012 KiB

mecho

// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
/* Abhi-Atg */
#define array int n;cin >> n;vector<long long> v(n);f(i,0,n)cin >> v[i];
#define out(_) for (auto &it :_){cout << it << " " ;}cout<<endl;
#define f(i,l,r) for(int i=l;i<r;i++)
#define ff(i,r,l) for(int i=r;i>=l;i--)
#define pb push_back
#define mod 1000000007
#define INDIA 998244353
#define ll long long 
#define all(v) v.begin(),v.end()
#define dbg cout << "Bharat\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define minus cout << "-1\n"

void solve(){
    int n,s;cin >> n >> s;
    vector<string> v(n);
    int mx,my;
    int dx,dy;
    vector<pair<int,int>> q;
    vector<vector<int>> dp(n,vector<int>(n, INDIA));
    f(i,0,n){
        cin >> v[i];
        for(int j=0;j<n;j++){
            if(v[i][j]=='M'){
                mx=i;my=j;
            }else if(v[i][j]=='D'){
                dx=i;dy=j;
            }else if(v[i][j]=='H'){
                q.pb({i,j});
                dp[i][j]=0;
            }
        }
    }
    int xx[]={0,0,1,-1};
    int yy[]={1,-1,0,0};
    for(int i=0;i<q.size();i++){
        for(int j=0;j<4;j++){
            int nx=q[i].first+xx[j];
            int ny=q[i].second+yy[j];
            if(nx>=0 && ny>=0 && nx<n && ny<n && v[nx][ny]!='T' && v[nx][ny]!='D' && dp[nx][ny]>dp[q[i].first][q[i].second]+1){
                dp[nx][ny]=dp[q[i].first][q[i].second]+1;
                q.pb({nx,ny});
            }
        }
    }
    int mn=-1;
    int l=0,r=INDIA;
    while(l<=r){
        int mid=(l+r)/2;
        bool flag=false;
        int val=mid;
        if(dp[mx][my]>val){
            vector<pair<int,int>> q;
            q.push_back({mx,my});
            vector<vector<bool>> vis(n,vector<bool>(n,false));
            vis[mx][my]=true;
            while(q.size()){
                val++;
                for(int st=0;st<s;st++){
                    vector<pair<int,int>> qq;
                    for(int i=0;i<q.size();i++){
                        for(int j=0;j<4;j++){
                            int nx=q[i].first+xx[j];
                            int ny=q[i].second+yy[j];
                            if(nx>=0 && ny>=0 && nx<n && ny<n && v[nx][ny]!='T' && vis[nx][ny]==false){
                                int cond=0;
                                if(st==s-1){
                                    cond=(dp[nx][ny]>val);
                                }else{
                                    cond=(dp[nx][ny]>=val);
                                }
                                if(cond){
                                    vis[nx][ny]=true;
                                    qq.pb({nx,ny});
                                    if(nx==dx && ny==dy){
                                        flag=true;
                                        break;
                                    }
                                }
                            }
                        }
                        if(flag)break;
                    }
                    q=qq;
                }
            }
        }
        if(flag){
            mn=mid;
            l=mid+1;
        }else r=mid-1;
    }
    cout << mn << "\n";
}


int main(){

    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif

    // freopen("input.in", "r", stdin);
    // freopen("output.out", "w", stdout);

    int t=1;
    // cin >> t;
    for(int _=1;_<=t;_++){
        // cout<<"Case #"<<_<<": ";
        solve();
    }

    return 0;
}

• Subtask 1: 100 / 100