Submission #138619

#	Time	Username	Problem	Language	Result	Execution time	Memory
138619		Boxworld	Mecho (IOI09_mecho)	C++14	6 / 100	1054 ms	65540 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MX=1000,inf=0x7fffffff;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char G[MX][MX];
int C[MX][MX],best[MX][MX];
int sx,sy,fx,fy,n,s,ans=-1;
queue<pii> Q[2];
queue<pair<pii,pii> > Q1;
int bfs(){
	best[sx][sy]=C[sx][sy];
	Q1.push(make_pair(make_pair(sx*MX+sy,0),make_pair(s,C[sx][sy])));
	while(!Q1.empty()){
		int maxtime=Q1.front().second.second;
		int xy=Q1.front().first.first;
		int time=Q1.front().first.second;
		int time1=Q1.front().second.first;
		Q1.pop();
		if (maxtime<ans)continue;
		int x=xy/MX,y=xy%MX;	
		if (time1>=s-1){
			time1=0;
			time++;
		}else time1++;
		for (int i=0;i<4;i++){
			int X=x+dx[i],Y=y+dy[i];
			if (X<1||X>n||Y<1||Y>n)continue;
			if (X==fx&&Y==fy){
				if (maxtime>ans)ans=maxtime;
		//		printf("NOW) x:%d y:%d ans=%d\n",X,Y,ans);
			}else{
			//	printf("x:%d y:%d time:%d(%d) mxtime:%d nowmax:%d best:%d\n",X,Y,time,time1,maxtime,C[X][Y]-time,best[X][Y]);
				if (C[X][Y]-time<max(0,ans))continue;
				if (C[X][Y]-time<best[X][Y])continue;
	//			printf("INQ(%2d) x:%d y:%d time:%d(%d) mxtime:%d nowmax:%d\n",Q1.size(),X,Y,time,time1,maxtime,C[X][Y]-time);
				best[X][Y]=C[X][Y]-time;
				Q1.push(make_pair(make_pair(X*MX+Y,time),make_pair(time1,min(maxtime,C[X][Y]-time))));
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&s);
	memset(C,-1,sizeof(C));
	memset(best,0,sizeof(best));
	for (int i=1;i<=n;i++){
		scanf("%s",G[i]+1);
		for (int j=1;j<=n;j++){
			if (G[i][j]=='H'){
				C[i][j]=0;
				Q[0].push(make_pair(i,j));
			}
			if (G[i][j]=='M')sx=i,sy=j;
			if (G[i][j]=='D')fx=i,fy=j,C[i][j]=inf;
		}
	}
	int cnt=0;
	for (int t=1;;t++){
		if (Q[cnt].empty())break;
		while(!Q[cnt].empty()){
			pii P=Q[cnt].front();Q[cnt].pop();
			int x=P.first,y=P.second;
			for (int i=0;i<4;i++){
				int X=x+dx[i],Y=y+dy[i];
				if (C[X][Y]>=0||G[X][Y]=='D'||G[X][Y]=='T')continue;
				C[X][Y]=t;
				Q[1-cnt].push(make_pair(X,Y));
			}
		}
		cnt=1-cnt;
	}
	bfs();
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int bfs()':
mecho.cpp:42:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
mecho.cpp: In function 'int main()':
mecho.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&s);
  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",G[i]+1);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 6 / 100