Submission #898210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
898210	2024-01-04T11:34:05 Z	lalig777	Mecho (IOI09_mecho)	C++14	14 / 100	1000 ms	65536 KB

mecho

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int iini, ifin, jini, jfin, n, s;

bool way_home(int m, vector<vector<int> >&bemoment, vector<vector<char> >&grid){
	queue<pair<int,int> >mecho;
	vector<vector<pair<int,int> > >mechomoment(n, vector<pair<int,int> >(n, make_pair(1e9, 0)));
	mecho.push(make_pair(iini, jini));
	mechomoment[iini][jini]=make_pair(m, 1);
	while (!mecho.empty()){
		int i=mecho.front().first;
		int j=mecho.front().second;
		mecho.pop();
		int minut=mechomoment[i][j].first, steps=mechomoment[i][j].second;
		if (steps==s){
			minut++;
			steps=0;
		}steps++;
		if ((i!=0 && grid[i-1][j]=='D')||(j!=0 && grid[i][j-1]=='D')||(i!=n-1 && grid[i+1][j]=='D')||((j!=n-1 && grid[i][j+1]=='D'))){
			return true;
		}
		if (i!=0 and bemoment[i-1][j]>minut){
			mechomoment[i-1][j]=make_pair(minut, steps);
			mecho.push(make_pair(i-1, j));
		}if (j!=0 and bemoment[i][j-1]>minut){
			mechomoment[i][j-1]=make_pair(minut, steps);
			mecho.push(make_pair(i, j-1));
		}if (i!=n-1 and bemoment[i+1][j]>minut){
			mechomoment[i+1][j]=make_pair(minut, steps);
			mecho.push(make_pair(i+1, j));
		}if (j!=n-1 and bemoment[i][j+1]>minut){
			mechomoment[i][j+1]=make_pair(minut, steps);
			mecho.push(make_pair(i, j+1));
		}
	}return false;

}

int main(){
	cin>>n>>s;
	vector<vector<char> >grid(n, vector<char>(n));
	vector<vector<int> >bemoment(n, vector<int>(n, 1e9));
	queue<pair<int,int> >grassy;
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			cin>>grid[i][j];
			if (grid[i][j]=='H'){
				grassy.push(make_pair(i, j));
				bemoment[i][j]=0;
			}else if (grid[i][j]=='M'){
				iini=i;
				jini=j;
			}else if (grid[i][j]=='D'){
				ifin=i;
				jfin=j;
				bemoment[i][j]=-1;
			}else if (grid[i][j]=='T') bemoment[i][j]=-1;
		}
	}while (!grassy.empty()){
		int i=grassy.front().first;
		int j=grassy.front().second;
		grassy.pop();
		if (i!=0 and bemoment[i-1][j]==1e9){
			bemoment[i-1][j]=bemoment[i][j]+1;
			grassy.push(make_pair(i-1, j));
		}if (j!=0 and bemoment[i][j-1]==1e9){
			bemoment[i][j-1]=bemoment[i][j]+1;
			grassy.push(make_pair(i, j-1));
		}if (i!=n-1 and bemoment[i+1][j]==1e9){
			bemoment[i+1][j]=bemoment[i][j]+1;
			grassy.push(make_pair(i+1, j));
		}if (j!=n-1 and bemoment[i][j+1]==1e9){
			bemoment[i][j+1]=bemoment[i][j]+1;
			grassy.push(make_pair(i, j+1));
		}
	}int ans=-1;
	int l=0, r=bemoment[iini][ifin]-1, m;
	while (l<=r){
		m=(r-l)/2+l;
		if (l+1==r){
			if (way_home(r, bemoment, grid)){
				ans=r;
				l+=2;
			}else if (way_home(l, bemoment, grid)){
				ans=l;
				r-=2;
			}else ans=-1;
			break;
		}
		if (way_home(m, bemoment, grid)) l=m;
		else r=m-1;
	}cout<<ans<<'\n';
	return 0;
}

Subtask #1

14.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1070 ms	348 KB	Time limit exceeded
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	0 ms	348 KB	Output isn't correct
6	Correct	3 ms	648 KB	Output is correct
7	Runtime error	142 ms	65536 KB	Execution killed with signal 9
8	Correct	0 ms	344 KB	Output is correct
9	Incorrect	0 ms	344 KB	Output isn't correct
10	Incorrect	0 ms	600 KB	Output isn't correct
11	Incorrect	1 ms	500 KB	Output isn't correct
12	Correct	0 ms	344 KB	Output is correct
13	Runtime error	140 ms	65536 KB	Execution killed with signal 9
14	Runtime error	130 ms	65536 KB	Execution killed with signal 9
15	Incorrect	1 ms	348 KB	Output isn't correct
16	Runtime error	402 ms	65536 KB	Execution killed with signal 9
17	Incorrect	0 ms	344 KB	Output isn't correct
18	Runtime error	173 ms	65536 KB	Execution killed with signal 9
19	Incorrect	1 ms	348 KB	Output isn't correct
20	Runtime error	164 ms	65536 KB	Execution killed with signal 9
21	Incorrect	0 ms	344 KB	Output isn't correct
22	Runtime error	171 ms	65536 KB	Execution killed with signal 9
23	Incorrect	0 ms	348 KB	Output isn't correct
24	Runtime error	166 ms	65536 KB	Execution killed with signal 9
25	Incorrect	1 ms	348 KB	Output isn't correct
26	Runtime error	188 ms	65536 KB	Execution killed with signal 9
27	Incorrect	1 ms	344 KB	Output isn't correct
28	Runtime error	171 ms	65536 KB	Execution killed with signal 9
29	Incorrect	1 ms	348 KB	Output isn't correct
30	Runtime error	168 ms	65536 KB	Execution killed with signal 9
31	Incorrect	1 ms	348 KB	Output isn't correct
32	Runtime error	170 ms	65536 KB	Execution killed with signal 9
33	Incorrect	5 ms	1112 KB	Output isn't correct
34	Runtime error	165 ms	65536 KB	Execution killed with signal 9
35	Runtime error	172 ms	65536 KB	Execution killed with signal 9
36	Incorrect	9 ms	1404 KB	Output isn't correct
37	Runtime error	172 ms	65536 KB	Execution killed with signal 9
38	Runtime error	169 ms	65536 KB	Execution killed with signal 9
39	Incorrect	9 ms	1628 KB	Output isn't correct
40	Runtime error	168 ms	65536 KB	Execution killed with signal 9
41	Runtime error	167 ms	65536 KB	Execution killed with signal 9
42	Incorrect	11 ms	1880 KB	Output isn't correct
43	Runtime error	169 ms	65536 KB	Execution killed with signal 9
44	Runtime error	172 ms	65536 KB	Execution killed with signal 9
45	Incorrect	13 ms	2140 KB	Output isn't correct
46	Runtime error	167 ms	65536 KB	Execution killed with signal 9
47	Runtime error	170 ms	65536 KB	Execution killed with signal 9
48	Incorrect	18 ms	2396 KB	Output isn't correct
49	Runtime error	168 ms	65536 KB	Execution killed with signal 9
50	Runtime error	172 ms	65536 KB	Execution killed with signal 9
51	Incorrect	20 ms	2904 KB	Output isn't correct
52	Runtime error	176 ms	65536 KB	Execution killed with signal 9
53	Runtime error	171 ms	65536 KB	Execution killed with signal 9
54	Incorrect	21 ms	3164 KB	Output isn't correct
55	Runtime error	169 ms	65536 KB	Execution killed with signal 9
56	Runtime error	182 ms	65536 KB	Execution killed with signal 9
57	Incorrect	27 ms	3764 KB	Output isn't correct
58	Runtime error	172 ms	65536 KB	Execution killed with signal 9
59	Runtime error	172 ms	65536 KB	Execution killed with signal 9
60	Incorrect	27 ms	4184 KB	Output isn't correct
61	Runtime error	177 ms	65536 KB	Execution killed with signal 9
62	Runtime error	176 ms	65536 KB	Execution killed with signal 9
63	Runtime error	179 ms	65536 KB	Execution killed with signal 9
64	Runtime error	179 ms	65536 KB	Execution killed with signal 9
65	Runtime error	183 ms	65536 KB	Execution killed with signal 9
66	Runtime error	185 ms	65536 KB	Execution killed with signal 9
67	Runtime error	181 ms	65536 KB	Execution killed with signal 9
68	Incorrect	35 ms	4188 KB	Output isn't correct
69	Incorrect	34 ms	4244 KB	Output isn't correct
70	Incorrect	36 ms	4188 KB	Output isn't correct
71	Incorrect	41 ms	4248 KB	Output isn't correct
72	Runtime error	180 ms	65536 KB	Execution killed with signal 9
73	Incorrect	30 ms	4444 KB	Output isn't correct
74	Incorrect	34 ms	4492 KB	Output isn't correct
75	Incorrect	31 ms	4388 KB	Output isn't correct
76	Incorrect	32 ms	4504 KB	Output isn't correct
77	Incorrect	38 ms	4628 KB	Output isn't correct
78	Runtime error	143 ms	65536 KB	Execution killed with signal 9
79	Runtime error	142 ms	65536 KB	Execution killed with signal 9
80	Runtime error	151 ms	65536 KB	Execution killed with signal 9
81	Runtime error	162 ms	65536 KB	Execution killed with signal 9
82	Runtime error	140 ms	65536 KB	Execution killed with signal 9
83	Runtime error	161 ms	65536 KB	Execution killed with signal 9
84	Runtime error	139 ms	65536 KB	Execution killed with signal 9
85	Runtime error	146 ms	65536 KB	Execution killed with signal 9
86	Runtime error	144 ms	65536 KB	Execution killed with signal 9
87	Runtime error	143 ms	65536 KB	Execution killed with signal 9
88	Runtime error	148 ms	65536 KB	Execution killed with signal 9
89	Runtime error	141 ms	65536 KB	Execution killed with signal 9
90	Runtime error	143 ms	65536 KB	Execution killed with signal 9
91	Runtime error	165 ms	65536 KB	Execution killed with signal 9
92	Runtime error	142 ms	65536 KB	Execution killed with signal 9