Submission #1154728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154728		murpyl	Mecho (IOI09_mecho)	C++20	89 / 100	391 ms	7088 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin); 
		freopen((name+".out").c_str(), "w", stdout);
	}
}
const int inf = 1e9;
const int maxn = 808;
int n, s;
char grid[maxn][maxn];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vi> dist(maxn, vi(maxn, inf));
vector<vi> beardist(maxn, vi(maxn, -1));
int sx, sy, ex, ey;

bool reachable(int mid){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            beardist[i][j] = -1;
        }
    }
    priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
    beardist[sx][sy] = 0;
    pq.push({0, {sx, sy}});
    while (!pq.empty()){
        auto [d, p] = pq.top();
        pq.pop();
        auto [x, y] = p;
        for (int i = 0; i < 4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] == 'T' || grid[nx][ny] == 'H') continue;
            if (beardist[nx][ny] != -1) continue;
            if ((d+1)/s >= dist[nx][ny]-mid) continue;
            beardist[nx][ny] = d+1;
            pq.push({d+1, {nx, ny}});
            
        }
    }
    for (int i = 0; i < 4; i++){
        int nx = ex+dx[i];
        int ny = ey+dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (beardist[nx][ny] != -1 && beardist[nx][ny]/s < dist[nx][ny]-mid) return true;
    }
    return false;
}


int main(){
    setIO();
    cin>>n>>s;
    priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin>>grid[i][j];
            if (grid[i][j] == 'H'){
                pq.push({0, {i, j}});
                dist[i][j] = 0;
            }
            if (grid[i][j] == 'M'){
                sx = i;
                sy = j;
            }
            if (grid[i][j] == 'D'){
                ex = i;
                ey = j;
            }
        }
    }
    while (!pq.empty()){
        auto [d, p] = pq.top();
        pq.pop();
        auto [x, y] = p;
        if (dist[x][y] < d) continue;
        for (int i = 0; i < 4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (grid[nx][ny] == 'T' || grid[nx][ny] == 'D') continue;
            if (dist[nx][ny] > d+1){
                dist[nx][ny] = d+1;
                pq.push({d+1, {nx, ny}});
            }
        }
    }
    int ans = -1;
    int l = 0, r = n*n;
    while (l <= r){
        int mid = (l+r)/2;
        if (reachable(mid)){
            ans = mid;
            l = mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

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

• Subtask 1: 89 / 100