Submission #1176450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176450		irmuun	Mecho (IOI09_mecho)	C++20	100 / 100	181 ms	31280 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,s;
    cin>>n>>s;
    auto a=vector(n,vector<char>(n));
    int mi,mj,di,dj;
    vector<pair<int,int>>h;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
            if(a[i][j]=='D'){
                di=i,dj=j;
            }
            if(a[i][j]=='M'){
                mi=i,mj=j;
            }
            if(a[i][j]=='H'){
                h.pb({i,j});
            }
        }
    }
    vector<int>dx={0,0,-1,1};
    vector<int>dy={-1,1,0,0};
    auto bee=vector(n,vector<int>(n,1e9));
    queue<pair<int,int>>q;
    for(auto [i,j]:h){
        bee[i][j]=0;
        q.push({i,j});
    }
    vector<pair<int,int>>g[n*n];
    while(!q.empty()){
        int i=q.front().ff,j=q.front().ss;
        int d=bee[i][j];
        q.pop();
        for(int k=0;k<4;k++){
            int ni=i+dx[k],nj=j+dy[k];
            if(ni<0||nj<0||ni>=n||nj>=n) continue;
            if(a[ni][nj]=='T'||a[ni][nj]=='D') continue;
            if(bee[i][j]+1<bee[ni][nj]){
                bee[ni][nj]=bee[i][j]+1;
                q.push({ni,nj});
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(bee[i][j]<1e9){
                g[bee[i][j]].pb({i,j});
            }
        }
    }
    int lo=-1,hi=n*n;
    vector<bool>used(n*n,false);
    while(lo<hi){
        int mid=(lo+hi+1)/2;
        auto dist=vector(n,vector<int>(n,1e9));
        queue<pair<int,int>>q;
        q.push({mi,mj});
        dist[mi][mj]=mid;
        int cur=0;
        bool ok=false;
        fill(all(used),false);
        while(!q.empty()){
            int i=q.front().ff,j=q.front().ss;
            int d=dist[i][j];
            if((d-mid)/s+mid>=bee[i][j]){
                q.pop();
                continue;
            }
            if(i==di&&j==dj){
                ok=true;
                break;
            }
            q.pop();
            for(int k=0;k<4;k++){
                int ni=i+dx[k],nj=j+dy[k];
                if(ni<0||nj<0||ni>=n||nj>=n) continue;
                if(a[ni][nj]=='T') continue;
                if(dist[i][j]+1<dist[ni][nj]){
                    dist[ni][nj]=dist[i][j]+1;
                    q.push({ni,nj});
                }
            }
        }
        if(ok) lo=mid;
        else hi=mid-1;
    }
    cout<<lo;
    return 0;
}

• Subtask 1: 100 / 100