Submission #709663

#	Time	Username	Problem	Language	Result	Execution time	Memory
709663		aggrovector	Mecho (IOI09_mecho)	C++17	100 / 100	187 ms	11612 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
long long n,s,i,j,d[805][805],x,y,vi[805][805],tl,tr,mid;
char a[805][805];
vector<pair<long long,long long>> h;
queue<pair<long long,long long>> q;
pair<long long,long long> st,e;
const long long INF=1e14;

int main() {
	cin >> n >> s;
	for (i=1;i<=n;i++) {
		for (j=1;j<=n;j++) {
			cin >> a[i][j];
			if (a[i][j]=='H') {
				h.push_back(make_pair(i,j));
			}
			if (a[i][j]=='M') {
				st=make_pair(i,j);
			}
			if (a[i][j]=='D') {
				e=make_pair(i,j);
			}
		}
	}
	for (i=0;i<h.size();i++) {
		q.push(make_pair(h[i].first,h[i].second));
		vi[h[i].first][h[i].second]=1;
	}
	while(!q.empty()) {
		x=q.front().first;
		y=q.front().second;
		q.pop();
		if (x>1 && vi[x-1][y]==0 && a[x-1][y]!='T' && a[x-1][y]!='D') {
			d[x-1][y]=d[x][y]+s;
			vi[x-1][y]=1;
			q.push(make_pair(x-1,y));
		}
		if (x<n && vi[x+1][y]==0 && a[x+1][y]!='T' && a[x+1][y]!='D') {
			d[x+1][y]=d[x][y]+s;
			vi[x+1][y]=1;
			q.push(make_pair(x+1,y));
		}
		if (y>1 && vi[x][y-1]==0 && a[x][y-1]!='T' && a[x][y-1]!='D') {
			d[x][y-1]=d[x][y]+s;
			vi[x][y-1]=1;
			q.push(make_pair(x,y-1));
		}
		if (y<n && vi[x][y+1]==0 && a[x][y+1]!='T' && a[x][y+1]!='D') {
			d[x][y+1]=d[x][y]+s;
			vi[x][y+1]=1;
			q.push(make_pair(x,y+1));
		}
	}
	d[e.first][e.second]=INF;
//	for (i=1;i<=n;i++) {
//		for (j=1;j<=n;j++) {
//			cout << d[i][j] << ' ';
//		}
//		cout << endl;
//	}
//	cout << endl;
	tl=0;
	tr=n*n;
	while(tl<tr) {
		mid=(tl+tr)/2+1;
		for (i=1;i<=n;i++) {
			for (j=1;j<=n;j++) {
				vi[i][j]=-1;
			}
		}
		if (d[st.first][st.second]<=mid*s) {
			tr=mid-1;
			continue;
		}
		q.push(st);
		vi[st.first][st.second]=0;
		while(!q.empty()) {
			x=q.front().first;
			y=q.front().second;
			q.pop();
			if (x>1 && vi[x-1][y]==-1 && a[x-1][y]!='T' && d[x-1][y]>vi[x][y]+1+mid*s) {
				vi[x-1][y]=vi[x][y]+1;
				q.push(make_pair(x-1,y));
			}
			if (x<n && vi[x+1][y]==-1 && a[x+1][y]!='T' && d[x+1][y]>vi[x][y]+1+mid*s) {
				vi[x+1][y]=vi[x][y]+1;
				q.push(make_pair(x+1,y));
			}
			if (y>1 && vi[x][y-1]==-1 && a[x][y-1]!='T' && d[x][y-1]>vi[x][y]+1+mid*s) {
				vi[x][y-1]=vi[x][y]+1;
				q.push(make_pair(x,y-1));
			}
			if (y<n && vi[x][y+1]==-1 && a[x][y+1]!='T' && d[x][y+1]>vi[x][y]+1+mid*s) {
				vi[x][y+1]=vi[x][y]+1;
				q.push(make_pair(x,y+1));
			}
		}
//		cout << tl << ' ' << tr << ' ' << mid << endl;
//		for (i=1;i<=n;i++) {
//			for (j=1;j<=n;j++) {
//				cout << vi[i][j] << ' ';
//			}
//			cout << endl;
//		}
//		cout << endl;
		if (vi[e.first][e.second]==-1) {
			tr=mid-1;
		}
		else {
			tl=mid;
		}
	}
	mid=tl;
	for (i=1;i<=n;i++) {
		for (j=1;j<=n;j++) {
			vi[i][j]=-1;
		}
	}
	if (d[st.first][st.second]<=mid*s) {
		cout << -1 << endl;
		return 0;
	}
	q.push(st);
	vi[st.first][st.second]=0;
	while(!q.empty()) {
		x=q.front().first;
		y=q.front().second;
		q.pop();
		if (x>1 && vi[x-1][y]==-1 && a[x-1][y]!='T' && d[x-1][y]>vi[x][y]+1+mid*s) {
			vi[x-1][y]=vi[x][y]+1;
			q.push(make_pair(x-1,y));
		}
		if (x<n && vi[x+1][y]==-1 && a[x+1][y]!='T' && d[x+1][y]>vi[x][y]+1+mid*s) {
			vi[x+1][y]=vi[x][y]+1;
			q.push(make_pair(x+1,y));
		}
		if (y>1 && vi[x][y-1]==-1 && a[x][y-1]!='T' && d[x][y-1]>vi[x][y]+1+mid*s) {
			vi[x][y-1]=vi[x][y]+1;
			q.push(make_pair(x,y-1));
		}
		if (y<n && vi[x][y+1]==-1 && a[x][y+1]!='T' && d[x][y+1]>vi[x][y]+1+mid*s) {
			vi[x][y+1]=vi[x][y]+1;
			q.push(make_pair(x,y+1));
		}
	}
	if (vi[e.first][e.second]==-1) {
		cout << -1 << endl;
	}
	else {
		cout << tl << endl;
	}
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:26:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (i=0;i<h.size();i++) {
      |           ~^~~~~~~~~

• Subtask 1: 100 / 100