Submission #138750

#	Time	Username	Problem	Language	Result	Execution time	Memory
138750		Boxworld	Mecho (IOI09_mecho)	C++14	96 / 100	245 ms	6648 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
const int N=810;
typedef pair<int,int> pii;
char G[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int T[N][N],d[N][N],vis[N][N];
int n,s,sx,sy;
int bfs(int time){
	if (time*s>=T[sx][sy])return 0;
	memset(vis,0,sizeof(vis));
	queue<pii> Q;
	vis[sx][sy]=1;
	Q.push(make_pair(sx*N+sy,time*s));
//	printf("X=%d Y=%d dis=%d\n",sx,sy,time*s);
	while(!Q.empty()){
		int dis=Q.front().second;
		int x=Q.front().first/N;
		int y=Q.front().first%N;
		Q.pop();
		if (G[x][y]=='D')return 1;
		
		for (int k=0;k<4;k++){
			int X=x+dx[k],Y=y+dy[k];
			if (X<1||X>N||Y<1||Y>N)continue;
			if (G[X][Y]=='T')continue;
			if (dis+1>=T[X][Y]||vis[X][Y])continue;
			vis[X][Y]=1;
			Q.push(make_pair(X*N+Y,dis+1));
	//		printf("X=%d Y=%d dis=%d\n",X,Y,dis+1);
		}
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;i++)scanf("%s",G[i]+1);
	memset(T,-1,sizeof(T));
	queue<int> bq;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++){
		if (G[i][j]=='M')sx=i,sy=j;
		if (G[i][j]=='D')T[i][j]=n*n*s;
		if (G[i][j]=='H'){
			T[i][j]=0;
			bq.push(i*N+j);
		}
	}
	while(!bq.empty()){
		int x=bq.front()/N,y=bq.front()%N;
		bq.pop();
		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||T[X][Y]!=-1)continue;
			if (G[X][Y]=='T'||G[X][Y]=='D')continue;
			T[X][Y]=T[x][y]+s;
			bq.push(X*N+Y);
		}
	}
	int l=-1,r=n*n*2;
	while(l+1<r){
		int m=(l+r)/2;
		if (bfs(m))l=m;
		else r=m;
	}
	printf("%d\n",l);
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:36: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:37:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1;i<=n;i++)scanf("%s",G[i]+1);
                        ~~~~~^~~~~~~~~~~~~

• Subtask 1: 96 / 100