Submission #92037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92037	2019-01-01T09:04:22 Z	arman_ferdous	Mecho (IOI09_mecho)	C++17	22 / 100	576 ms	66560 KB

mecho

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> ii;
const int N = 1001;
const int inf = 2e9;
 
int n, S, d[N][N], dist[N][N];
string s[N];
queue<ii> q;
ii mecho, home;
 
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
 
bool can(int T) {
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			dist[i][j] = inf;
	if(T * S >= d[mecho.first][mecho.second]) return false;
 
	q.push(mecho);
	dist[mecho.first][mecho.second] = T * S;
	ii u; int arrival, tx, ty;
	while(!q.empty()) {
		u = q.front(); q.pop();
		for(int i = 0; i < 4; i++) {
			tx = u.first + dx[i], ty = u.second + dy[i];
			if(min(tx,ty) < 0 || max(tx,ty) >= n) continue;
			if(s[tx][ty] != 'G' && s[tx][ty] != 'D') continue;
			arrival = dist[u.first][u.second] + 1;
			if(arrival >= d[tx][ty] || arrival > dist[tx][ty]) continue;
			dist[tx][ty] = dist[u.first][u.second] + 1;
			q.push({tx,ty});
		}
	} 
	return dist[home.first][home.second] != inf;
}
 
int main() {
	cin >> n >> S;
	for(int i = 0; i < n; i++)
		cin >> s[i];
 
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) {
			d[i][j] = inf;
			if(s[i][j] == 'M') mecho = {i,j};
			else if(s[i][j] == 'D') home = {i,j};
		}
	s[mecho.first][mecho.second] = 'G';
 
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) 
			if(s[i][j] == 'H') {
				q.push({i,j});
				d[i][j] = 0;
			}
 
	while(!q.empty()) {
		ii u = q.front(); q.pop();
		for(int i = 0; i < 4; i++) {
			int tx = u.first + dx[i], ty = u.second + dy[i];
			if(min(tx,ty) < 0 || max(tx,ty) >= n) continue;
			if(s[tx][ty] != 'G') continue;
			if(d[tx][ty] < d[u.first][u.second] + S) continue;
			d[tx][ty] = d[u.first][u.second] + S;
			q.push({tx,ty});
		}
	}
	int lo = 0, hi = n + n, ans = -1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(can(mid)) ans = mid, lo = mid+1;
		else hi = mid-1;
	} cout << ans << "\n";
	return 0;
}

Subtask #1

22.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Runtime error	345 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Correct	2 ms	504 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Incorrect	2 ms	888 KB	Output isn't correct
13	Runtime error	453 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	469 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Incorrect	2 ms	504 KB	Output isn't correct
16	Incorrect	2 ms	504 KB	Output isn't correct
17	Incorrect	2 ms	632 KB	Output isn't correct
18	Incorrect	2 ms	632 KB	Output isn't correct
19	Incorrect	2 ms	632 KB	Output isn't correct
20	Incorrect	2 ms	632 KB	Output isn't correct
21	Incorrect	2 ms	632 KB	Output isn't correct
22	Incorrect	2 ms	708 KB	Output isn't correct
23	Incorrect	2 ms	760 KB	Output isn't correct
24	Incorrect	2 ms	760 KB	Output isn't correct
25	Incorrect	3 ms	888 KB	Output isn't correct
26	Incorrect	2 ms	760 KB	Output isn't correct
27	Incorrect	2 ms	888 KB	Output isn't correct
28	Incorrect	3 ms	888 KB	Output isn't correct
29	Incorrect	3 ms	888 KB	Output isn't correct
30	Incorrect	3 ms	932 KB	Output isn't correct
31	Incorrect	2 ms	888 KB	Output isn't correct
32	Incorrect	3 ms	1016 KB	Output isn't correct
33	Incorrect	15 ms	3320 KB	Output isn't correct
34	Incorrect	22 ms	3320 KB	Output isn't correct
35	Runtime error	300 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Incorrect	19 ms	3704 KB	Output isn't correct
37	Incorrect	26 ms	3704 KB	Output isn't correct
38	Runtime error	283 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Incorrect	24 ms	4088 KB	Output isn't correct
40	Incorrect	57 ms	4088 KB	Output isn't correct
41	Runtime error	298 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Incorrect	29 ms	4728 KB	Output isn't correct
43	Incorrect	39 ms	4728 KB	Output isn't correct
44	Runtime error	289 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Incorrect	37 ms	5116 KB	Output isn't correct
46	Incorrect	50 ms	5240 KB	Output isn't correct
47	Runtime error	298 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Incorrect	42 ms	5624 KB	Output isn't correct
49	Incorrect	62 ms	5752 KB	Output isn't correct
50	Runtime error	319 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Incorrect	51 ms	6140 KB	Output isn't correct
52	Incorrect	74 ms	6140 KB	Output isn't correct
53	Runtime error	311 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Incorrect	59 ms	6572 KB	Output isn't correct
55	Incorrect	86 ms	6556 KB	Output isn't correct
56	Runtime error	327 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Incorrect	67 ms	6904 KB	Output isn't correct
58	Incorrect	104 ms	6904 KB	Output isn't correct
59	Runtime error	314 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Incorrect	77 ms	7416 KB	Output isn't correct
61	Incorrect	113 ms	7416 KB	Output isn't correct
62	Runtime error	315 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Correct	139 ms	7416 KB	Output is correct
64	Correct	188 ms	7436 KB	Output is correct
65	Correct	198 ms	7416 KB	Output is correct
66	Correct	151 ms	7440 KB	Output is correct
67	Correct	132 ms	7432 KB	Output is correct
68	Correct	71 ms	7416 KB	Output is correct
69	Correct	65 ms	7416 KB	Output is correct
70	Correct	58 ms	7416 KB	Output is correct
71	Correct	59 ms	7524 KB	Output is correct
72	Correct	51 ms	7408 KB	Output is correct
73	Runtime error	576 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	516 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	550 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	513 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	543 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	510 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	522 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	506 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	500 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	511 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	441 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	399 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	449 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	435 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	402 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	344 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	344 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	362 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	347 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	352 ms	66560 KB	Execution killed with signal 9 (could be triggered by violating memory limits)