답안 #92081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92081	2019-01-01T11:58:18 Z	arman_ferdous	Mecho (IOI09_mecho)	C++17	100 / 100	315 ms	7812 KB

mecho

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

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

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

int n, S;
string mat[N];

int beeDist[N][N], d[N][N];
bool vis[N][N];
int Mx, My, Dx, Dy;
queue< pair<int,int> > Q;

bool call(int T) {
	if(T * S >= beeDist[Mx][My]) return false;
	for(int i = 0; i < n; i++) 
		for(int j = 0; j < n; j++)
			vis[i][j] = false;

	vis[Mx][My] = true; d[Mx][My] = T * S;
	Q.push(make_pair(Mx,My));
	while(!Q.empty()) {
		auto it = Q.front(); Q.pop();
		int ux = it.first, uy = it.second;
		for(int k = 0; k < 4; k++) {
			int tx = ux + dx[k], ty = uy + dy[k];
			if(min(tx,ty) < 0 || max(tx,ty) >= n || mat[tx][ty] == 'T' || mat[tx][ty] == 'H' || vis[tx][ty] || d[ux][uy] + 1 >= beeDist[tx][ty]) continue;
			vis[tx][ty] = 1; d[tx][ty] = d[ux][uy] + 1; Q.push(make_pair(tx,ty));
		}
	} return vis[Dx][Dy];
}

int main() {
	cin >> n >> S;
	for(int i = 0; i < n; i++) cin >> mat[i];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			beeDist[i][j] = INF;
			if(mat[i][j] == 'M') Mx = i, My = j;
			else if(mat[i][j] == 'D') Dx = i, Dy = j;
			else if(mat[i][j] == 'H') {
				Q.push(make_pair(i,j));
				beeDist[i][j] = 0;
			}
		}
	}
	while(!Q.empty()) {
		auto it = Q.front(); Q.pop();
		int ux = it.first, uy = it.second;
		for(int k = 0; k < 4; k++) {
			int tx = ux + dx[k];
			int ty = uy + dy[k];
			if(min(tx,ty) < 0 || max(tx,ty) >= n || mat[tx][ty] == 'T' || mat[tx][ty] == 'D' || beeDist[ux][uy] + S >= beeDist[tx][ty]) continue;
			beeDist[tx][ty] = beeDist[ux][uy] + S;
			Q.push(make_pair(tx,ty));
		}
	}
	int lo = 0, hi = n * n, ans = -1;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(call(mid)) ans = mid, lo = mid+1;
		else hi = mid-1;
	} cout << ans << "\n";
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 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	Correct	149 ms	6520 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	2 ms	508 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	632 KB	Output is correct
13	Correct	2 ms	552 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	504 KB	Output is correct
18	Correct	2 ms	476 KB	Output is correct
19	Correct	2 ms	504 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	632 KB	Output is correct
24	Correct	2 ms	632 KB	Output is correct
25	Correct	10 ms	636 KB	Output is correct
26	Correct	2 ms	632 KB	Output is correct
27	Correct	2 ms	760 KB	Output is correct
28	Correct	2 ms	760 KB	Output is correct
29	Correct	2 ms	636 KB	Output is correct
30	Correct	2 ms	760 KB	Output is correct
31	Correct	2 ms	760 KB	Output is correct
32	Correct	2 ms	760 KB	Output is correct
33	Correct	9 ms	2168 KB	Output is correct
34	Correct	10 ms	2424 KB	Output is correct
35	Correct	29 ms	3184 KB	Output is correct
36	Correct	12 ms	2424 KB	Output is correct
37	Correct	13 ms	2780 KB	Output is correct
38	Correct	35 ms	3576 KB	Output is correct
39	Correct	14 ms	2680 KB	Output is correct
40	Correct	14 ms	3064 KB	Output is correct
41	Correct	50 ms	4088 KB	Output is correct
42	Correct	17 ms	3192 KB	Output is correct
43	Correct	17 ms	3576 KB	Output is correct
44	Correct	63 ms	4728 KB	Output is correct
45	Correct	20 ms	3448 KB	Output is correct
46	Correct	20 ms	3960 KB	Output is correct
47	Correct	83 ms	4984 KB	Output is correct
48	Correct	22 ms	3740 KB	Output is correct
49	Correct	24 ms	4344 KB	Output is correct
50	Correct	118 ms	5496 KB	Output is correct
51	Correct	23 ms	4088 KB	Output is correct
52	Correct	27 ms	4476 KB	Output is correct
53	Correct	165 ms	6008 KB	Output is correct
54	Correct	32 ms	4344 KB	Output is correct
55	Correct	33 ms	4856 KB	Output is correct
56	Correct	178 ms	6520 KB	Output is correct
57	Correct	36 ms	4600 KB	Output is correct
58	Correct	38 ms	5112 KB	Output is correct
59	Correct	213 ms	6928 KB	Output is correct
60	Correct	39 ms	4856 KB	Output is correct
61	Correct	41 ms	5496 KB	Output is correct
62	Correct	243 ms	7516 KB	Output is correct
63	Correct	150 ms	6776 KB	Output is correct
64	Correct	315 ms	6904 KB	Output is correct
65	Correct	243 ms	6848 KB	Output is correct
66	Correct	196 ms	6904 KB	Output is correct
67	Correct	182 ms	6776 KB	Output is correct
68	Correct	74 ms	6776 KB	Output is correct
69	Correct	73 ms	6748 KB	Output is correct
70	Correct	52 ms	6776 KB	Output is correct
71	Correct	60 ms	6748 KB	Output is correct
72	Correct	49 ms	4956 KB	Output is correct
73	Correct	55 ms	7644 KB	Output is correct
74	Correct	96 ms	7812 KB	Output is correct
75	Correct	127 ms	7672 KB	Output is correct
76	Correct	101 ms	7672 KB	Output is correct
77	Correct	89 ms	7676 KB	Output is correct
78	Correct	105 ms	6264 KB	Output is correct
79	Correct	75 ms	6008 KB	Output is correct
80	Correct	87 ms	6264 KB	Output is correct
81	Correct	98 ms	6136 KB	Output is correct
82	Correct	92 ms	6136 KB	Output is correct
83	Correct	108 ms	6264 KB	Output is correct
84	Correct	100 ms	6320 KB	Output is correct
85	Correct	129 ms	6236 KB	Output is correct
86	Correct	128 ms	6388 KB	Output is correct
87	Correct	129 ms	6328 KB	Output is correct
88	Correct	130 ms	6540 KB	Output is correct
89	Correct	120 ms	6392 KB	Output is correct
90	Correct	121 ms	6368 KB	Output is correct
91	Correct	134 ms	6420 KB	Output is correct
92	Correct	135 ms	6380 KB	Output is correct