Submission #1310549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310549		StefanSebez	Mecho (IOI09_mecho)	C++20	100 / 100	163 ms	7172 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=810,inf=1e9;
vector<pair<int,int>>ds={{0,1},{0,-1},{1,0},{-1,0}};
int n,S;
string a[N];
int dist1[N][N];
bool was[N][N];
bool Check(int i,int j){
    if(i<0||i>=n||j<0||j>=n)return false;
    if(a[i][j]=='T'||was[i][j])return false;
    return true;
}
int dist[N][N],dist2[N][N];
bool BFS(int t){
    queue<pair<int,int>>kju;
    int U,V;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
        dist[i][j]=inf;was[i][j]=false;
        if(a[i][j]=='M')dist[i][j]=0,was[i][j]=true,kju.push({i,j});
        if(a[i][j]=='D')U=i,V=j;
    }
    while(!kju.empty()){
        auto [i,j]=kju.front();kju.pop();
        for(auto [dx,dy]:ds)if(Check(i+dx,j+dy)){
            if((dist[i][j]%S!=S-1&&dist[i][j]/S+1<=dist1[i+dx][j+dy]-t)||(dist[i][j]%S==S-1&&dist[i][j]/S+1<dist1[i+dx][j+dy]-t)){
                dist[i+dx][j+dy]=dist[i][j]+1;
                kju.push({i+dx,j+dy});
                was[i+dx][j+dy]=true;
            }
        }
    }
    return dist[U][V]<inf;
}
int main(){
    scanf("%i%i",&n,&S);
    for(int i=0;i<n;i++)cin>>a[i];
    queue<pair<int,int>>kju;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
        dist1[i][j]=inf;
        if(a[i][j]=='H')dist1[i][j]=0,kju.push({i,j}),was[i][j]=true;
    }
    while(!kju.empty()){
        auto [i,j]=kju.front();kju.pop();
        for(auto [dx,dy]:ds)if(Check(i+dx,j+dy)&&a[i+dx][j+dy]!='D'){
            dist1[i+dx][j+dy]=dist1[i][j]+1;
            kju.push({i+dx,j+dy});
            was[i+dx][j+dy]=true;
        }
    }
    int U,V;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(a[i][j]=='M')U=i,V=j;
    int l=0,r=dist1[U][V]-1,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(BFS(mid))res=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%i%i",&n,&S);
      |     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100