Submission #701534

#	Time	Username	Problem	Language	Result	Execution time	Memory
701534		starplat	Mecho (IOI09_mecho)	C++14	95 / 100	265 ms	8216 KiB

mecho

#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
int n,S,vis[805][805],tim[805][805];
pair<int,int> st,ed,bck[805][805];
char c[805][805];
vector<pair<int,int>> d,path;
queue<pair<pair<int,int>,pair<int,int>>> q;
bool ok(int x,int y){
	return (1<=x && x<=n && 1<=y && y<=n);
}
bool pass(int T){
	T*=S;
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) vis[i][j]=0;
	queue<pair<pair<int,int>,int>> t; t.push(mp(st,T));
	while (!t.empty()){
		auto x=t.front(); t.pop();
		if (x.f==ed) vis[x.f.f][x.f.s]=x.s;
		else if (x.s>=(tim[x.f.f][x.f.s]-1)*S || vis[x.f.f][x.f.s]) continue;
		vis[x.f.f][x.f.s]=x.s;
		for (auto k:d){
			int a=x.f.f+k.f; int b=x.f.s+k.s;
			if (ok(a,b) && c[a][b]!='T') t.push(mp(mp(a,b),x.s+1));
		}
	}
	return vis[ed.f][ed.s];
}
int main() {
	cin>>n>>S;
	d.push_back({1,0}); d.push_back({-1,0});
	d.push_back({0,-1}); d.push_back({0,1});
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>c[i][j];
			if (c[i][j]=='D') ed=mp(i,j);
			if (c[i][j]=='M') st=mp(i,j);
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (c[i][j]=='H') q.push(mp(mp(i,j),mp(0,0)));
		}
	}
	while (!q.empty()){
		auto x=q.front(); q.pop();
		if (tim[x.f.f][x.f.s]) continue;
		tim[x.f.f][x.f.s]=tim[x.s.f][x.s.s]+1;
		for (auto k:d){
			int a=x.f.f+k.f; int b=x.f.s+k.s;
			if (ok(a,b) && c[a][b]!='T') q.push(mp(mp(a,b),x.f));
		}
	}
	tim[ed.f][ed.s]=INT_MAX;
	if (pass(0)){
		int ans=0;
		int l=0; int r=n*n+5;
		while (l<=r){
			int mid=(l+r)/2;
			if (pass(mid)){
				ans=mid; l=mid+1;
			}
			else r=mid-1;
		}
		cout<<ans<<"\n";
	}
	else cout<<"-1\n";
}

• Subtask 1: 95 / 100