Submission #696121

#	Time	Username	Problem	Language	Result	Execution time	Memory
696121		North1304	Mecho (IOI09_mecho)	C++17	12 / 100	246 ms	65536 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
char str[801][801];
int dism[801][801],disb[801][801],n,s;
int rm,cm,rd,cd;
vector<pair<int,int>> dir = {{-1,0},{0,-1},{1,0},{0,1}};
queue<tuple<int,int,int>> q;
queue<pair<int,int>> Q;
bool solve(int t) {
	if (t>=disb[rm][cm]) return false;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			dism[i][j] = INF;
		}
	}
	dism[rm][cm] = t;
	q.push({rm, cm, 0});
	while (!q.empty()) {
		auto [x,y,cou] = q.front(); q.pop();
		if (dism[x][y]==INF) continue;
		for(auto [di,dj]:dir) {
			int xx = x + di, yy = y + dj;
			int next = dism[x][y] + ((cou+1)%s == 0);
			if (xx<1 || xx>n || yy<1 || yy>n || str[xx][yy]=='T') continue;
			if (next < disb[xx][yy]) {
				dism[xx][yy] = next;
				q.push({xx, yy, cou+1});
			} 
		}
	}
	return dism[rd][cd] != INF;
}

int main(){
	cin >> n >> s;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cin >> str[i][j];
			dism[i][j] = disb[i][j] = INF;
			if (str[i][j]=='M') rm = i, cm = j;
			else if (str[i][j]=='D') rd = i, cd = j;
			else if (str[i][j]=='H') {
				disb[i][j] = 0;
				Q.push({i, j});
			}
		}
	}
	while (!Q.empty()) {
		auto [a,b] = Q.front(); Q.pop();
		for(auto [di,dj]:dir) {
			int aa = a + di, bb = b + dj;
			if (aa<1 || aa>n || bb<1 || bb>n || str[aa][bb]=='T' || str[aa][bb]=='D') continue;
			if (disb[aa][bb]>disb[a][b]+1) {
				disb[aa][bb] = disb[a][b]+1;
				Q.push({aa,bb});
			}
		}
	}
	int l=1,r=n*n,ans;
	while (l<r) {
		int mid = (l + r) / 2;
		if (solve(mid)) l = mid + 1, ans = mid; 
		else r = mid - 1;
	}
	cout << ans;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:66:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  cout << ans;
      |          ^~~

• Subtask 1: 12 / 100