Submission #1121103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121103		sktodow	Mecho (IOI09_mecho)	C++17	68 / 100	550 ms	12884 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'));}
bool isvis(int i,int j){ return i/s<j;}


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=0;i<n;i++){
        for(int j=0;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});}
        }
    }
    int l=0,r=n*n;
    while(l<=r){
        vector<vector<int>>mec(N,vector<int>(N));
        vector<vector<int>>bee(N, vector<int>(N));
        vector<vector<bool>>vis(N,vector<bool>(N));
        vector<vector<bool>>vis2(N, vector<bool>(N));
        
        queue<array<int,2>> q;

        int curr=(l+r)/2;

        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]<=curr){q.pop();}

        while(!q.empty()){
            int x=q.front()[0],y=q.front()[1];
            q.pop();
            for(int i=0;i<4;i++){
                int cx=x+dx[i],cy=y+dy[i];
                if(inside(cx,cy) && !vis[cx][cy] && isvis(mec[x][y]+1,bee[cx][cy]-curr)){
                    vis[cx][cy]=1;
                    mec[cx][cy]=mec[x][y]+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) && isvis(mec[cx][cy],bee[cx][cy]-curr) && vis[cx][cy]){chc=1;}
        }

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