Submission #1275174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275174		khoianh	Mecho (IOI09_mecho)	C++20	84 / 100	885 ms	17160 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 1e3 + 5;
ll dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
ll n, s, ex, ey, sx, sy, b[mn][mn], c[mn][mn];
char a[mn][mn];
struct node{
	ll x, y, ti;
};
queue<node> q;

bool check(ll mid){
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(a[i][j] == 'H')q.push({i, j, 0});
			 b[i][j] = c[i][j] = -1;
		} 
	}
	while(!q.empty()){
		node t = q.front();
		q.pop();
		if(c[t.x][t.y] != -1) continue;
		c[t.x][t.y] = t.ti;
		if(a[t.x][t.y] != 'G' && a[t.x][t.y] != 'H' && a[t.x][t.y] != 'M') continue;
		for(int i = 0; i < 4; ++i){
			if(t.x + dx[i] < 0 || t.x + dx[i] > n || t.y + dy[i] < 0 || t.y + dy[i] > n) continue;
			q.push({t.x + dx[i], t.y + dy[i], t.ti + s});
		}
	}
	q.push({sx, sy, mid * s});
	while(!q.empty()){
		node t = q.front();
		q.pop();
		if(b[t.x][t.y] != -1) continue;
		b[t.x][t.y] = t.ti;
		if(a[t.x][t.y] == 'T') continue;
		if(b[t.x][t.y] >= c[t.x][t.y] && c[t.x][t.y] != -1) continue;
		for(int i = 0; i < 4; ++i){
			if(t.x + dx[i] < 0 || t.x + dx[i] > n || t.y + dy[i] < 0 || t.y + dy[i] > n) continue;
			q.push({t.x + dx[i], t.y + dy[i], t.ti + 1});
		}
	}
//	for(int i = 1; i <= n; ++i){
//		for(int j = 1; j <= n; ++j) cout << b[i][j] << " ";
//		cout << "\n";
//	}
//	for(int i = 1; i <= n; ++i){
//		for(int j = 1; j <= n; ++j) cout << c[i][j] << " ";
//		cout << "\n";
//	}
//	cout << c[ex][ey] << " " << mid << " " << b[ex][ey] << "\n";
	return !(b[ex][ey] == -1 || (b[ex][ey] >= c[ex][ey] && c[ex][ey] != -1));
}

void solve(){
	cin >> n >> s;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j) cin >> a[i][j];
	}
//	cout << "yumyum" << endl;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(a[i][j] == 'M') sx = i, sy = j;
			if(a[i][j] == 'D') ex = i, ey = j;
		}
	}
	ll l = 0, r = 1e9, mid;
	while(l <= r){
		mid = (l + r) / 2;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << r << "\n";
    return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if(fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	int testCase = 1;
	//cin >> testCase;
	while(testCase--) solve();
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:82:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:83:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 84 / 100