Submission #1119718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119718		sktodow	Mecho (IOI09_mecho)	C++17	73 / 100	254 ms	8492 KiB

mecho

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
// #define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=805;
static const long long int MOD=(1LL<<61)-1;
static const long long int inf=INT64_MAX;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
void io(string name = ""){ 
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}
 
int n,x,mx,my;
vector<vector<char>>v(N,vector<char>(N));
vector<vector<int>>bee(N,vector<int>(N,-1));
int mec[N][N];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
 
bool inside(int a,int b){return ((a<=n && a>0)&&(b<=n && b>0)&&v[a][b]!='T');}
 
void calcbee(){
    queue<array<int,3>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(v[i][j]=='H'){q.push({i,j,0});}
        }
    }
    while(q.size()){
        array<int,3>curr=q.front();
        q.pop();
        if(bee[curr[0]][curr[1]]!=-1){continue;}
        bee[curr[0]][curr[1]]=curr[2];
        for(int i=0;i<4;i++){
            if(inside(curr[0]+dx[i],curr[1]+dy[i])){
                q.push({curr[0]+dx[i],curr[1]+dy[i],curr[2]+1});
            }
        }
    }
}
 
bool mecho(int k){
    queue<array<int,3>>q;
    q.push({mx,my,k});
    while(q.size()){
        array<int,3>curr=q.front();
        q.pop();
        if(mec[curr[0]][curr[1]]!=-1){continue;}
        
        mec[curr[0]][curr[1]]=curr[2];
        if(v[curr[0]][curr[1]]=='D'){return 1;}
        for(int i=0;i<4;i++){
            if(inside(curr[0]+dx[i],curr[1]+dy[i]) && bee[curr[0]+dx[i]][curr[1]+dy[i]]>(curr[2]+1)/x){
                q.push({curr[0]+dx[i],curr[1]+dy[i],curr[2]+1});
            }
        }
    }
    return 0;
}
 
int32_t main(){
    //io("local");
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>v[i][j];
            if(v[i][j]=='M'){mx=i,my=j;}
        }
    }
    calcbee();
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){cout<<bee[i][j]<<" ";}
    //     cout<<endl;
    // }
    int l=0,r=n*n;
    bool chc=0,achc=0;
    while(l<=r){
        memset(mec,-1,sizeof(mec));
        chc=mecho(mid*(x));
        // cout<<mid<<" "<<chc<<endl;
        if(chc){l=mid+1;achc=1;}
        else{r=mid-1;}
        
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=n;j++){cout<<mec[i][j]<<" ";}
        //     cout<<endl;
        // }
        // cout<<endl;
    }
    memset(mec,-1,sizeof(mec));
    if(!achc && mecho(0)){cout<<0;}
    else if(!achc){cout<<-1;}
    else{cout<<l-1;}
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void io(std::string)':
mecho.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 73 / 100