Submission #1121096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121096		sktodow	Mecho (IOI09_mecho)	C++17	63 / 100	525 ms	12792 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 int MOD=(1LL<<61)-1;
static const 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,s,mx,my,hx,hy;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

vector<vector<char>>v(N,vector<char>(N));


bool inside(int i,int j){ return ((i>0&&i<=n) && (j>0&&j<=n) && (v[i][j]=='M' || v[i][j]=='G'));}


int32_t main(){
    //io("local");
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin>>n>>s;
    vector<array<int,2>>h;
    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;}
            if(v[i][j]=='D'){hx=i,hy=j;}
            if(v[i][j]=='H'){h.pb({i,j});}
        }
    }
    // 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 aaa=0;
    while(l<=r){
        vector<vector<int>>mec(N,vector<int>(N));
        vector<vector<bool>>vis(N,vector<bool>(N));
        vector<vector<bool>> vis2(N, vector<bool>(N));
        vector<vector<int>> bee(N, vector<int>(N));
        queue<array<int,2>> q;

        for(auto i:h) {
            q.push({i[0],i[1]});
            vis2[i[0]][i[1]] = 1;
        }
        while(!q.empty()) {
            int x=q.front()[0], y=q.front()[1];
            q.pop();
            for (int i=0;i<4;i++) {
                int nx=x+dx[i], ny=y+dy[i];
                if (inside(nx,ny) && !vis2[nx][ny]) {
                    bee[nx][ny]=bee[x][y] + 1;
                    q.push({nx,ny});
                    vis2[nx][ny]=1;
                }
            }
        }

        vis[mx][my]=1;
        q.push({mx,my});
        if(bee[mx][my]<=mid){q.pop();}
        while(q.size()){
            array<int,2>c=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int cx=c[0]+dx[i],cy=c[1]+dy[i];
                // cout<<c[2]/s<<" ";
                if(inside(cx,cy) && !vis[cx][cy] && (mec[c[0]][c[1]]+1)/s < bee[cx][cy]-mid){
                    vis[cx][cy]=1;
                    mec[cx][cy]=mec[c[0]][c[1]]+1;
                    q.push({cx,cy});
                }
            }
        }


        bool chc=0;
        for(int i=0;i<n;i++){
            int cx=hx+dx[i],cy=hy+dy[i];
            if(inside(cx,cy) && mec[cx][cy]/s<bee[cx][cy] && vis[cx][cy]){chc=1;aaa=1;}
        }
        // cout<<mid<<" "<<chc<<endl;
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=n;j++){
        //         cout<<mec[i][j]<<" ";
        //     }cout<<endl;
        // }

        if(chc){l=mid+1;}
        else{r=mid-1;}
    }
    if(aaa){cout<<l-1;}
    else{cout<<-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: 63 / 100