Submission #980551

#	Time	Username	Problem	Language	Result	Execution time	Memory
980551		BF001	Mecho (IOI09_mecho)	C++17	69 / 100	143 ms	6492 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define N 805
#define fi first
#define se second

typedef pair<int, int> ii;

int n, d[N][N], d1[N][N], xs, ys, xe, ye, s; 
vector<ii> o;
char a[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool in(int u, int v){
	return u >= 1 && u <= n && v >= 1 && v <= n && a[u][v] != 'T'; 
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    queue<ii> q;

    cin >> n >> s;
    
    for (int i = 1; i <= n; i++){
    	for (int j = 1; j <= n; j++){
    		d1[i][j] = d[i][j] = 1e9;
    	}
    }

    for (int i = 1; i <= n; i++){
    	for (int j = 1; j <= n; j++){
    		cin >> a[i][j];
    		if (a[i][j] == 'H') {
    			d1[i][j] = 0;
    			q.push({i, j});
    		}
    		if (a[i][j] == 'D'){
    			xe = i;
    			ye = j;
    		} 
    		if (a[i][j] == 'M'){
    			xs = i;
    			ys = j;
    		}
    	}
    }

    while (!q.empty()){
    	int u = q.front().fi;
    	int v = q.front().se;
    	q.pop();
    	for (int i = 0; i <= 3; i++){
    		int newu = u + dx[i];
    		int newv = v + dy[i];
    		if (!in(newu, newv)) continue;
    		if (newu == xe && newv == ye) continue;
    		if (d1[newu][newv] > d1[u][v] + 1){
    			d1[newu][newv] = d1[u][v] + 1;
    			q.push({newu, newv});
    		}
    	}
    }

    int l = 1, r = n * n, rt = -1;
    while (l <= r){
    	int mid = (l + r) >> 1;
    	for (int i = 1; i <= n; i++){
    		for (int j = 1; j <= n; j++) d[i][j] = 1e9;
    	}
    	d[xs][ys] = 0;
    	q.push({xs, ys});
		while (!q.empty()){
    		int u = q.front().fi;
    		int v = q.front().se;
    		q.pop();
    		for (int i = 0; i <= 3; i++){
    			int newu = u + dx[i];
    			int newv = v + dy[i];
    			if (!in(newu, newv)) continue;
    			int newd = mid + (d[u][v] + 1) / s;
    			if (d1[newu][newv] <= newd) continue;
    			if (d[newu][newv] > d[u][v] + 1){
    				d[newu][newv] = d[u][v] + 1;
    				q.push({newu, newv});
    			}
    		}
    	}
    	if (d[xe][ye] != 1e9) {rt = mid; l = mid + 1;}
    	else r = mid - 1;
    }

    cout << rt;

    return 0;
}     

• Subtask 1: 69 / 100