Submission #295849

#	Time	Username	Problem	Language	Result	Execution time	Memory
295849		Hemimor	Mecho (IOI09_mecho)	C++14	84 / 100	310 ms	7040 KiB

mecho

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,m;
vvi b;
vs a;

bool f(int t){
	queue<P> q;
	vvi c(n,vi(n,inf));
	int gx,gy;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++){
		if(a[i][j]=='M'){
			q.push({i,j});
			c[i][j]=0;
			if(t>=b[i][j]) return 0;
		}
		if(a[i][j]=='D') gx=i,gy=j;
	}
	while(!q.empty()){
		P p=q.front();q.pop();
		int i=p.first,j=p.second;
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(x>=0&&x<n&&y>=0&&y<n&&a[x][y]!='T'&&c[x][y]==inf&&t+(c[i][j]+1)/m<b[x][y]){
				q.push({x,y});
				c[x][y]=c[i][j]+1;
			}
		}
	}
	return c[gx][gy]<inf;
}

int main(){
	cin>>n>>m;
	a=vs(n);
	b=vvi(n,vi(n,inf));
	for(auto &i:a) cin>>i;
	queue<P> q;
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(a[i][j]=='H'){
		b[i][j]=0;
		q.push({i,j});
	}
	while(!q.empty()){
		P p=q.front();q.pop();
		int i=p.first,j=p.second;
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(x>=0&&x<n&&y>=0&&y<n&&a[x][y]!='T'&&b[x][y]==inf){
				q.push({x,y});
				b[x][y]=b[i][j]+1;
			}
		}
	}
	int l=-1,r=n*n;
	while(r-l>1){
		int m=(l+r)/2;
		if(f(m)) l=m;
		else r=m;
	}
	cout<<l<<endl;
}

Compilation message (stderr)

mecho.cpp: In function 'bool f(int)':
mecho.cpp:65:17: warning: 'gy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  return c[gx][gy]<inf;
      |                 ^
mecho.cpp:65:13: warning: 'gx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  return c[gx][gy]<inf;
      |             ^

• Subtask 1: 84 / 100