Submission #217540

#	Time	Username	Problem	Language	Result	Execution time	Memory
217540		t12345	Mecho (IOI09_mecho)	C++14	84 / 100	225 ms	9592 KiB

mecho

#include <iostream>
#include <cstdio>
#include <queue>
#define N 805
#define PR pair<int, int>
#define F first
#define S second
using namespace std;

int n, k, mi, mj, di, dj, v[N][N], x[N][N], y[N][N];
int lt, rt, md, ans;
char a[N][N];
queue<PR> qu;
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};

int f(int p) {
	int i, j, r, c, t;
	for(i=0; i<n; i++) for(j=0; j<n; j++) v[i][j] = 0;
	while(!qu.empty()) qu.pop();
	y[mi][mj] = p * k;
	if(y[mi][mj] < x[mi][mj]) {
		v[mi][mj] = 1;
		qu.push({mi, mj});
	}
	while(!qu.empty()) {
		r = qu.front().F;
		c = qu.front().S;
		qu.pop();
		for(t=0; t<4; t++) {
			i = r + dr[t];
			j = c + dc[t];
			if(0<=i && i<n && 0<=j && j<n && y[r][c]+1 < x[i][j] && !v[i][j] && (a[i][j]=='G' || a[i][j]=='D')) {
				v[i][j] = 1;
				y[i][j] = y[r][c] + 1;
				qu.push({i, j});
			}
		}
	}
	return v[di][dj];
}

int main() {
	int i, j, r, c, t;
	cin >> n >> k;
	for(i=0; i<n; i++) {
		cin >> a[i];
		for(j=0; j<n; j++) {
			x[i][j] = 1e9;
			if(a[i][j]=='H') {
				x[i][j] = 0;
				v[i][j] = 1;
				qu.push({i,j});
			}
			else if(a[i][j]=='M') mi=i, mj=j;
			else if(a[i][j]=='D') di=i, dj=j;
		}
	}
	while(!qu.empty()) {
		r = qu.front().F;
		c = qu.front().S;
		qu.pop();
		for(t=0; t<4; t++) {
			i = r + dr[t];
			j = c + dc[t];
			if(0<=i && i<n && 0<=j && j<n && !v[i][j] && (a[i][j]=='G' || a[i][j]=='M')) {
				v[i][j] = 1;
				x[i][j] = x[r][c] + k;
				qu.push({i, j});
			}
		}
	}
	rt = n*n;
	while(lt <= rt) {
		md = lt+rt >> 1;
		if(f(md)) ans=md, lt=md+1;
		else rt=md-1;
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:75:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   md = lt+rt >> 1;
        ~~^~~

• Subtask 1: 84 / 100