Submission #92036

# Submission time Handle Problem Language Result Execution time Memory
92036 2019-01-01T08:54:14 Z arman_ferdous Mecho (IOI09_mecho) C++14
22 / 100
539 ms 66560 KB
#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];
char s[N][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() {
	scanf("%d %d", &n, &S);
	for(int i = 0; i < n; i++)
		scanf(" %s", 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;
	} printf("%d\n", ans);
	return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:41: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:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", s[i]);
   ~~~~~^~~~~~~~~~~~~
# 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 376 KB Output is correct
7 Runtime error 330 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 417 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 431 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 504 KB Output isn't correct
18 Incorrect 2 ms 504 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 632 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 2 ms 888 KB Output isn't correct
26 Incorrect 2 ms 888 KB Output isn't correct
27 Incorrect 2 ms 888 KB Output isn't correct
28 Incorrect 2 ms 888 KB Output isn't correct
29 Incorrect 3 ms 1016 KB Output isn't correct
30 Incorrect 3 ms 1020 KB Output isn't correct
31 Incorrect 3 ms 1016 KB Output isn't correct
32 Incorrect 3 ms 1016 KB Output isn't correct
33 Incorrect 12 ms 3448 KB Output isn't correct
34 Incorrect 18 ms 3448 KB Output isn't correct
35 Runtime error 276 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Incorrect 15 ms 3832 KB Output isn't correct
37 Incorrect 22 ms 3832 KB Output isn't correct
38 Runtime error 278 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Incorrect 19 ms 4344 KB Output isn't correct
40 Incorrect 27 ms 4344 KB Output isn't correct
41 Runtime error 276 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Incorrect 21 ms 4728 KB Output isn't correct
43 Incorrect 31 ms 4728 KB Output isn't correct
44 Runtime error 266 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Incorrect 27 ms 5240 KB Output isn't correct
46 Incorrect 40 ms 5240 KB Output isn't correct
47 Runtime error 263 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Incorrect 32 ms 5624 KB Output isn't correct
49 Incorrect 47 ms 5624 KB Output isn't correct
50 Runtime error 297 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Incorrect 39 ms 6136 KB Output isn't correct
52 Incorrect 58 ms 6136 KB Output isn't correct
53 Runtime error 276 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Incorrect 46 ms 6652 KB Output isn't correct
55 Incorrect 76 ms 6576 KB Output isn't correct
56 Runtime error 282 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Incorrect 49 ms 6904 KB Output isn't correct
58 Incorrect 84 ms 6904 KB Output isn't correct
59 Runtime error 298 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Incorrect 55 ms 7416 KB Output isn't correct
61 Incorrect 83 ms 7416 KB Output isn't correct
62 Runtime error 260 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Correct 92 ms 7416 KB Output is correct
64 Correct 144 ms 7428 KB Output is correct
65 Correct 171 ms 7416 KB Output is correct
66 Correct 113 ms 7544 KB Output is correct
67 Correct 97 ms 7424 KB Output is correct
68 Correct 52 ms 7416 KB Output is correct
69 Correct 42 ms 7452 KB Output is correct
70 Correct 39 ms 7416 KB Output is correct
71 Correct 38 ms 7416 KB Output is correct
72 Correct 33 ms 7416 KB Output is correct
73 Runtime error 488 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 539 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 490 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 488 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 497 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 420 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 426 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 423 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 414 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 470 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 370 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 366 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 370 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 371 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 361 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 315 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 353 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Runtime error 361 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
91 Runtime error 356 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 318 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)