Submission #418027

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
418027	2021-06-04T22:21:25 Z	gromperen	Mecho (IOI09_mecho)	C++17	12 / 100	303 ms	16096 KB

mecho

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int INF = 1e9+69;
const int MAXN = 800;

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

vector<string> G(MAXN);
vector<vector<int>> G2(MAXN, vector<int>(MAXN,INF));
vector<vector<int>> G3(MAXN, vector<int>(MAXN,INF));

int n;
int s;

int sx, sy, ex, ey;

bool possible(int wait) {
	queue <tuple<int,int,int>> q;


	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			G3[i][j] = -1;
		}
	}
	if (wait * s >= G2[sx][sy]) {
		//cout << "BRUH" << endl;
		return false;
	}
	q.push({wait*s, sx, sy});
	while (!q.empty()) {
		int w = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		//if (G[x][y] == 'D') {
			//cout << "YEH"<< endl;
		//}
		q.pop();
		if (G3[x][y] != -1) continue;
		G3[x][y] = w;
		for (int i = 0; i < 4 ;++i) {
			if (x + dx[i] < 0
					|| x + dx[i] >= n
					|| y + dy[i] < 0
					|| y + dy[i] >= n
					|| (G[x+dx[i]][y+dy[i]] == 'T')
					|| w+1 >= G2[x+dx[i]][y+dy[i]] ) {
				if (G[x+dx[i]][y+dy[i]] == 'D')
					q.push({w+1, x+dx[i], y+dy[i]});
				continue;
			}
			q.push({w+1, x+dx[i], y+dy[i]});
		}
	}
	//cout << endl;
	//cout << wait << endl;
	//for (int i = 0; i < n; ++i) {
		//for (int j = 0; j < n; ++j) {
			//cout << G3[i][j] << " ";
		//}
		//cout << endl;
	//}


	return G3[ex][ey] != -1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	 cin >> n;
	 cin >> s;
	for (int i = 0; i < n; ++i) {
		cin >> G[i];
	}
	queue<tuple<int,int,int>> q;
	for (int i = 0; i < n; ++i) {
		for (int j  =0; j < n; ++j) {
			if (G[i][j] == 'H') {
				//G2[i][j] = 0;
				G2[i][j] = -1;
				q.push({0, i,j});
			} else {
				G2[i][j] = -1;
			}
			if (G[i][j] == 'M') {
				sx = i;
				sy = j;
			}
			if (G[i][j] == 'D') {
				ex = i;
				ey = j;
			}
		}
	}
	while(!q.empty()) {
		int w = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		q.pop();
		if (G2[x][y] != -1) continue;
		G2[x][y] = w;
		for (int i = 0; i < 4; ++i) {
			if (x + dx[i] < 0
					|| x + dx[i] >= n
					|| y + dy[i] < 0
					|| y + dy[i] >= n
					|| (G[x+dx[i]][y+dy[i]] != 'G' && G[x+dx[i]][y+dy[i]] != 'M')) {
				continue;
			}
			q.push({w+s, x+dx[i], y+dy[i]});
		}
	}

	//for (int i = 0; i < n; ++i) {
		//for (int j  =0; j < n; ++j) {
			//cout << G2[i][j] << " ";
		//}
		//cout << endl;
	//}


	if (!possible(0)) {
		cout << "-1\n";
		return 0;
	}

	int l = 0, h = MAXN * MAXN, m;
	while(l < h) {
		m = (l + h) / 2 + 1;
		if (possible(m)) {
			l = m;
		} else {
			h = m - 1;
		}
	}
	cout << l << "\n";

	return 0;
}

Subtask #1

12.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	10768 KB	Execution killed with signal 11
2	Runtime error	8 ms	10692 KB	Execution killed with signal 11
3	Runtime error	9 ms	10744 KB	Execution killed with signal 11
4	Runtime error	8 ms	10700 KB	Execution killed with signal 11
5	Runtime error	8 ms	10788 KB	Execution killed with signal 11
6	Runtime error	8 ms	10700 KB	Execution killed with signal 11
7	Runtime error	62 ms	14020 KB	Execution killed with signal 11
8	Correct	3 ms	5324 KB	Output is correct
9	Runtime error	8 ms	10700 KB	Execution killed with signal 11
10	Correct	3 ms	5324 KB	Output is correct
11	Correct	3 ms	5324 KB	Output is correct
12	Runtime error	8 ms	10700 KB	Execution killed with signal 11
13	Correct	3 ms	5324 KB	Output is correct
14	Correct	3 ms	5324 KB	Output is correct
15	Runtime error	8 ms	10692 KB	Execution killed with signal 11
16	Runtime error	8 ms	10748 KB	Execution killed with signal 11
17	Runtime error	8 ms	10700 KB	Execution killed with signal 11
18	Runtime error	8 ms	10700 KB	Execution killed with signal 11
19	Runtime error	8 ms	10700 KB	Execution killed with signal 11
20	Runtime error	9 ms	10768 KB	Execution killed with signal 11
21	Runtime error	8 ms	10700 KB	Execution killed with signal 11
22	Runtime error	8 ms	10700 KB	Execution killed with signal 11
23	Runtime error	8 ms	10732 KB	Execution killed with signal 11
24	Runtime error	8 ms	10700 KB	Execution killed with signal 11
25	Runtime error	8 ms	10700 KB	Execution killed with signal 11
26	Runtime error	9 ms	10700 KB	Execution killed with signal 11
27	Runtime error	10 ms	10700 KB	Execution killed with signal 11
28	Runtime error	9 ms	10700 KB	Execution killed with signal 11
29	Runtime error	9 ms	10800 KB	Execution killed with signal 11
30	Runtime error	9 ms	10700 KB	Execution killed with signal 11
31	Runtime error	8 ms	10700 KB	Execution killed with signal 11
32	Runtime error	9 ms	10724 KB	Execution killed with signal 11
33	Runtime error	11 ms	11156 KB	Execution killed with signal 11
34	Runtime error	13 ms	11132 KB	Execution killed with signal 11
35	Correct	59 ms	5580 KB	Output is correct
36	Runtime error	13 ms	11212 KB	Execution killed with signal 11
37	Runtime error	16 ms	11244 KB	Execution killed with signal 11
38	Correct	76 ms	5744 KB	Output is correct
39	Runtime error	14 ms	11340 KB	Execution killed with signal 11
40	Runtime error	19 ms	11340 KB	Execution killed with signal 11
41	Correct	99 ms	5832 KB	Output is correct
42	Runtime error	15 ms	11512 KB	Execution killed with signal 11
43	Runtime error	20 ms	11440 KB	Execution killed with signal 11
44	Correct	123 ms	5920 KB	Output is correct
45	Runtime error	17 ms	11596 KB	Execution killed with signal 11
46	Runtime error	23 ms	11648 KB	Execution killed with signal 11
47	Correct	150 ms	6044 KB	Output is correct
48	Runtime error	19 ms	11824 KB	Execution killed with signal 11
49	Runtime error	27 ms	11908 KB	Execution killed with signal 11
50	Correct	183 ms	6212 KB	Output is correct
51	Runtime error	20 ms	12108 KB	Execution killed with signal 11
52	Runtime error	28 ms	12036 KB	Execution killed with signal 11
53	Correct	219 ms	6220 KB	Output is correct
54	Runtime error	21 ms	12236 KB	Execution killed with signal 11
55	Runtime error	31 ms	12232 KB	Execution killed with signal 11
56	Correct	270 ms	6404 KB	Output is correct
57	Runtime error	23 ms	12492 KB	Execution killed with signal 11
58	Runtime error	34 ms	12484 KB	Execution killed with signal 11
59	Correct	303 ms	6584 KB	Output is correct
60	Runtime error	26 ms	12720 KB	Execution killed with signal 11
61	Runtime error	27 ms	12744 KB	Execution killed with signal 11
62	Runtime error	52 ms	12868 KB	Execution killed with signal 11
63	Runtime error	42 ms	12720 KB	Execution killed with signal 11
64	Runtime error	41 ms	12752 KB	Execution killed with signal 11
65	Runtime error	41 ms	12708 KB	Execution killed with signal 11
66	Runtime error	42 ms	12740 KB	Execution killed with signal 11
67	Runtime error	41 ms	12684 KB	Execution killed with signal 11
68	Runtime error	47 ms	12928 KB	Execution killed with signal 11
69	Runtime error	50 ms	13052 KB	Execution killed with signal 11
70	Runtime error	46 ms	12872 KB	Execution killed with signal 11
71	Runtime error	46 ms	12924 KB	Execution killed with signal 11
72	Runtime error	45 ms	12872 KB	Execution killed with signal 11
73	Runtime error	67 ms	16012 KB	Execution killed with signal 11
74	Runtime error	68 ms	16068 KB	Execution killed with signal 11
75	Runtime error	68 ms	15928 KB	Execution killed with signal 11
76	Runtime error	73 ms	16096 KB	Execution killed with signal 11
77	Runtime error	71 ms	16028 KB	Execution killed with signal 11
78	Correct	78 ms	8128 KB	Output is correct
79	Correct	181 ms	8068 KB	Output is correct
80	Correct	198 ms	8172 KB	Output is correct
81	Correct	216 ms	8112 KB	Output is correct
82	Correct	187 ms	8132 KB	Output is correct
83	Runtime error	64 ms	15204 KB	Execution killed with signal 11
84	Correct	235 ms	7920 KB	Output is correct
85	Correct	241 ms	7836 KB	Output is correct
86	Correct	220 ms	7912 KB	Output is correct
87	Correct	226 ms	7884 KB	Output is correct
88	Runtime error	63 ms	14656 KB	Execution killed with signal 11
89	Correct	275 ms	7556 KB	Output is correct
90	Correct	253 ms	7620 KB	Output is correct
91	Correct	296 ms	7632 KB	Output is correct
92	Correct	285 ms	7596 KB	Output is correct