Submission #892945

#	Time	Username	Problem	Language	Result	Execution time	Memory
892945		ilef	Mecho (IOI09_mecho)	C++14	8 / 100	149 ms	26296 KiB

mecho

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int inf=INT_MAX;
 int n,s;
 bool safe(int i,int j){
     return i>=0 && i<n && j>=0 && j<n;
 }
 int di[4]={0,0,-1,1};
 int dj[4]={1,-1,0,0};
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  
    cin>>n>>s;
    char mat[n][n];
    int dist1[n][n];
    int dist2[n][n];
    int homex,homey;
    //vector<pair<int,int>>hives;
    int honx,hony;
    queue<pair<int,int>>q;
    bool vis1[n][n];
    bool vis2[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            vis1[i][j]=false;
            vis2[i][j]=false;
            dist1[i][j]=inf;
            dist2[i][j]=inf;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mat[i][j];
            if(mat[i][j]=='M'){
                honx=i;
                hony=j;
            }
            if(mat[i][j]=='D'){
                homex=i;
                homey=j;
            }
            if(mat[i][j]=='H'){
                q.push({i,j});
                dist1[i][j]=0;
                vis1[i][j]=true;
            }
        }
    }
    while(!q.empty()){
        const auto &[i,j]=q.front();
        q.pop();
        for(int l=0;l<4;l++){
            int x=i+di[l];
            int y=j+dj[l];
            if(safe(x,y) && !vis1[x][y] && (mat[x][y]=='G'||mat[x][y]=='M')){
                dist1[x][y]=dist1[i][j]+1;
                vis1[x][y]=true;
                q.push({x,y});
            }
        }
    }
    bool reached=false;
    int ll=0,rr=1e6;
    while(ll+1<rr){
        int mid=(ll+rr)/2;
          for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
            vis2[i][j]=false;
             dist2[i][j]=inf;
            
        }
    }
        dist2[honx][hony]=mid;
        if(dist2[honx][hony]<dist1[honx][hony]){
            vis2[honx][hony]=true;
            q.push({honx,hony});
        }
        while(!q.empty()){
        const auto &[i,j]=q.front();
        q.pop();
        for(int l=0;l<4;l++){
            int x=i+di[l];
            int y=j+dj[l];
                    if(safe(x,y) && (mat[x][y]=='G'|| mat[x][y]=='D')&& !vis2[x][y] && (((dist2[i][j]+1)/s)<dist1[x][y])){
                        dist2[x][y]=dist2[i][j]+1;
                        vis2[x][y]=true;
                        q.push({x,y});
                    }
                }
             
                }
            
    if(dist2[homex][homey]<inf){
        reached=true;
        ll=mid;
    }
    else{
        rr=mid;
    }
    }
    if(reached){
       cout<<ll-2<<endl;
    }
    else{
        cout<<-1<<endl;
    }
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:53:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         const auto &[i,j]=q.front();
      |                     ^
mecho.cpp:82:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |         const auto &[i,j]=q.front();
      |                     ^
mecho.cpp:76:26: warning: 'hony' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         dist2[honx][hony]=mid;
      |         ~~~~~~~~~~~~~~~~~^~~~
mecho.cpp:76:26: warning: 'honx' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:96:26: warning: 'homex' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     if(dist2[homex][homey]<inf){
      |        ~~~~~~~~~~~~~~~~~~^
mecho.cpp:96:26: warning: 'homey' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 8 / 100