답안 #103687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103687	2019-04-02T04:29:47 Z	turbat	Mecho (IOI09_mecho)	C++14	31 / 100	921 ms	3888 KB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using pii = pair<int, int>;
using vi = vector <int>;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define ook order_of_key
#define fbo find_by_order
#define sq(x) (x) * (x)
#define N 805

int x, y, posx, posy, n, s;
int ax[4] = {0, 0, 1, -1};
int ay[4] = {1, -1, 0, 0}; 
string st[N];
queue <pii> que, q, bfs, mecho;
bool used[N][N], vis[N][N], pass[N][N];

bool check(int curx, int cury){
	if (curx < n && cury < n && curx >= 0 && cury >= 0 && !used[curx][cury]) return true;
	return false;
}

bool can(int time){;
	que = q;
	mecho.push(mp(x, y));
	memset(pass, 0, sizeof pass);
	pass[x][y] = 1;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++)
			used[i][j] = vis[i][j];
	while (time--){
		bfs = que;
		while(!que.empty()) que.pop();
		while (!bfs.empty()){
			pii pos = bfs.front();
			bfs.pop();
			for (int i = 0;i < 4;i++)
				if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T')
					que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
		} 
	}
	while (!used[posx][posy]){
		int tmp = s;
		while (tmp--){
			bfs = mecho;
			while (!mecho.empty()) mecho.pop();
			while (!bfs.empty()){
				pii pos = bfs.front();
				bfs.pop();
				if (pos.F == posx && pos.S == posy) return true;			
				if (!used[pos.F][pos.S])
					for (int i = 0;i < 4;i++)
						if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T'
							&& !pass[pos.F + ax[i]][pos.S + ay[i]])
							mecho.push(mp(pos.F + ax[i], pos.S + ay[i])), pass[pos.F + ax[i]][pos.S + ay[i]] = 1;
			}
		}
		bfs = que;
		while (!que.empty()) que.pop();
		while (!bfs.empty()){
			pii pos = bfs.front();
			bfs.pop();
			for (int i = 0;i < 4;i++)
				if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T')
					que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
		} 
	}
	return false;
}

int main (){
	cin >> n>> s;
	for (int i = 0;i < n;i++)
		cin >> st[i];
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++){
			if (st[i][j] == 'M') x = i, y = j;
			if (st[i][j] == 'D') posx = i, posy = j;
			if (st[i][j] == 'H') q.push(mp(i, j)), vis[i][j] = 1;
		}
	int l = 0, r = n * n;
	while (l != r){
		int mid = (l + r + 1) / 2;
		if (can(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l;
}

Subtask #1

31.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1024 KB	Output is correct
2	Incorrect	3 ms	1024 KB	Output isn't correct
3	Correct	3 ms	1024 KB	Output is correct
4	Incorrect	3 ms	1024 KB	Output isn't correct
5	Correct	3 ms	1024 KB	Output is correct
6	Incorrect	3 ms	1024 KB	Output isn't correct
7	Incorrect	437 ms	2936 KB	Output isn't correct
8	Incorrect	3 ms	1024 KB	Output isn't correct
9	Correct	3 ms	1152 KB	Output is correct
10	Correct	3 ms	1024 KB	Output is correct
11	Correct	3 ms	1024 KB	Output is correct
12	Incorrect	4 ms	1024 KB	Output isn't correct
13	Correct	4 ms	1024 KB	Output is correct
14	Incorrect	5 ms	1152 KB	Output isn't correct
15	Correct	3 ms	1024 KB	Output is correct
16	Correct	3 ms	1024 KB	Output is correct
17	Correct	3 ms	1024 KB	Output is correct
18	Correct	3 ms	1024 KB	Output is correct
19	Correct	3 ms	1024 KB	Output is correct
20	Correct	3 ms	1024 KB	Output is correct
21	Correct	4 ms	1024 KB	Output is correct
22	Correct	3 ms	1024 KB	Output is correct
23	Correct	5 ms	1024 KB	Output is correct
24	Correct	4 ms	1024 KB	Output is correct
25	Correct	5 ms	1024 KB	Output is correct
26	Correct	5 ms	1152 KB	Output is correct
27	Correct	5 ms	1024 KB	Output is correct
28	Correct	6 ms	1024 KB	Output is correct
29	Correct	6 ms	1024 KB	Output is correct
30	Correct	4 ms	1024 KB	Output is correct
31	Correct	7 ms	1024 KB	Output is correct
32	Correct	5 ms	1024 KB	Output is correct
33	Correct	145 ms	1408 KB	Output is correct
34	Correct	46 ms	1528 KB	Output is correct
35	Incorrect	38 ms	1484 KB	Output isn't correct
36	Correct	162 ms	1656 KB	Output is correct
37	Correct	65 ms	1536 KB	Output is correct
38	Incorrect	47 ms	1536 KB	Output isn't correct
39	Correct	173 ms	1536 KB	Output is correct
40	Correct	120 ms	1536 KB	Output is correct
41	Incorrect	54 ms	1656 KB	Output isn't correct
42	Correct	246 ms	1912 KB	Output is correct
43	Correct	123 ms	1912 KB	Output is correct
44	Incorrect	78 ms	1920 KB	Output isn't correct
45	Correct	329 ms	1992 KB	Output is correct
46	Correct	172 ms	1912 KB	Output is correct
47	Incorrect	96 ms	2096 KB	Output isn't correct
48	Correct	352 ms	2048 KB	Output is correct
49	Correct	140 ms	2168 KB	Output is correct
50	Correct	117 ms	2208 KB	Output is correct
51	Correct	442 ms	2296 KB	Output is correct
52	Correct	203 ms	2168 KB	Output is correct
53	Incorrect	144 ms	2296 KB	Output isn't correct
54	Correct	582 ms	2380 KB	Output is correct
55	Correct	215 ms	2296 KB	Output is correct
56	Incorrect	146 ms	2176 KB	Output isn't correct
57	Correct	921 ms	2340 KB	Output is correct
58	Correct	264 ms	2296 KB	Output is correct
59	Incorrect	191 ms	2396 KB	Output isn't correct
60	Correct	737 ms	2552 KB	Output is correct
61	Correct	282 ms	2552 KB	Output is correct
62	Incorrect	221 ms	2524 KB	Output isn't correct
63	Correct	616 ms	2548 KB	Output is correct
64	Correct	666 ms	2440 KB	Output is correct
65	Correct	586 ms	2552 KB	Output is correct
66	Correct	500 ms	2432 KB	Output is correct
67	Incorrect	557 ms	2552 KB	Output isn't correct
68	Correct	469 ms	3192 KB	Output is correct
69	Correct	419 ms	3164 KB	Output is correct
70	Correct	517 ms	3192 KB	Output is correct
71	Correct	505 ms	3320 KB	Output is correct
72	Correct	431 ms	3088 KB	Output is correct
73	Correct	428 ms	3888 KB	Output is correct
74	Incorrect	441 ms	3852 KB	Output isn't correct
75	Incorrect	381 ms	3640 KB	Output isn't correct
76	Incorrect	404 ms	3764 KB	Output isn't correct
77	Correct	424 ms	3832 KB	Output is correct
78	Incorrect	445 ms	3280 KB	Output isn't correct
79	Correct	364 ms	3264 KB	Output is correct
80	Incorrect	452 ms	3348 KB	Output isn't correct
81	Incorrect	385 ms	3360 KB	Output isn't correct
82	Incorrect	376 ms	3412 KB	Output isn't correct
83	Incorrect	417 ms	3204 KB	Output isn't correct
84	Correct	538 ms	3384 KB	Output is correct
85	Incorrect	458 ms	3280 KB	Output isn't correct
86	Incorrect	385 ms	3240 KB	Output isn't correct
87	Incorrect	402 ms	3212 KB	Output isn't correct
88	Incorrect	369 ms	3080 KB	Output isn't correct
89	Correct	436 ms	3208 KB	Output is correct
90	Incorrect	395 ms	3184 KB	Output isn't correct
91	Correct	388 ms	3068 KB	Output is correct
92	Incorrect	424 ms	3288 KB	Output isn't correct