Submission #138619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138619	2019-07-30T07:28:01 Z	Boxworld	Mecho (IOI09_mecho)	C++14	6 / 100	1000 ms	65540 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	8184 KB	Output isn't correct
2	Incorrect	30 ms	8184 KB	Output isn't correct
3	Incorrect	31 ms	8248 KB	Output isn't correct
4	Incorrect	32 ms	8312 KB	Output isn't correct
5	Correct	31 ms	8184 KB	Output is correct
6	Correct	31 ms	8184 KB	Output is correct
7	Runtime error	170 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Incorrect	31 ms	8184 KB	Output isn't correct
9	Correct	38 ms	9336 KB	Output is correct
10	Correct	32 ms	8312 KB	Output is correct
11	Correct	32 ms	8312 KB	Output is correct
12	Incorrect	36 ms	8184 KB	Output isn't correct
13	Runtime error	308 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	257 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Incorrect	31 ms	8184 KB	Output isn't correct
16	Incorrect	31 ms	8184 KB	Output isn't correct
17	Incorrect	33 ms	8228 KB	Output isn't correct
18	Incorrect	33 ms	8440 KB	Output isn't correct
19	Incorrect	31 ms	8184 KB	Output isn't correct
20	Incorrect	38 ms	9564 KB	Output isn't correct
21	Incorrect	30 ms	8184 KB	Output isn't correct
22	Incorrect	242 ms	43316 KB	Output isn't correct
23	Incorrect	37 ms	8056 KB	Output isn't correct
24	Runtime error	245 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Incorrect	34 ms	8312 KB	Output isn't correct
26	Runtime error	251 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Incorrect	31 ms	8184 KB	Output isn't correct
28	Runtime error	242 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
29	Incorrect	33 ms	8284 KB	Output isn't correct
30	Runtime error	227 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
31	Incorrect	31 ms	8316 KB	Output isn't correct
32	Runtime error	230 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
33	Incorrect	32 ms	8440 KB	Output isn't correct
34	Runtime error	226 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
35	Runtime error	209 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Incorrect	33 ms	8568 KB	Output isn't correct
37	Runtime error	248 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
38	Runtime error	210 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Incorrect	31 ms	8568 KB	Output isn't correct
40	Runtime error	224 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
41	Runtime error	213 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Incorrect	35 ms	8696 KB	Output isn't correct
43	Runtime error	228 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
44	Runtime error	207 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Incorrect	32 ms	8696 KB	Output isn't correct
46	Runtime error	227 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
47	Runtime error	210 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	33 ms	8744 KB	Output isn't correct
49	Runtime error	233 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
50	Runtime error	211 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Incorrect	31 ms	8824 KB	Output isn't correct
52	Runtime error	223 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Runtime error	211 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Incorrect	32 ms	8824 KB	Output isn't correct
55	Runtime error	230 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
56	Runtime error	208 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Incorrect	31 ms	8952 KB	Output isn't correct
58	Runtime error	251 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
59	Runtime error	219 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Incorrect	30 ms	8952 KB	Output isn't correct
61	Runtime error	241 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
62	Runtime error	214 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Incorrect	43 ms	8952 KB	Output isn't correct
64	Runtime error	226 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
65	Incorrect	59 ms	9080 KB	Output isn't correct
66	Incorrect	47 ms	8952 KB	Output isn't correct
67	Correct	50 ms	8976 KB	Output is correct
68	Runtime error	234 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
69	Runtime error	222 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
70	Runtime error	510 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
71	Execution timed out	1054 ms	12068 KB	Time limit exceeded
72	Runtime error	238 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
73	Runtime error	165 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	180 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	168 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	176 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	165 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	259 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	167 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	267 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	164 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	169 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	187 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	171 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	172 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	167 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	171 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	166 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	181 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	165 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	171 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	170 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)