답안 #516234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516234	2022-01-20T17:44:41 Z	Tizariox	Mecho (IOI09_mecho)	C++14	46 / 100	1000 ms	53636 KB

mecho

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

using ll = long long;
using pii = pair<int, int>;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define F0R1(i, a) for (int i = 1; i <= (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd1(i, a) for (int i = a; i > 0; i--)
#define SORT(vec) sort(vec.begin(), vec.end())
#define S0RT(arr, n) sort(arr, arr + n)

#define pA first
#define pB second
#define MOD 1000000007
#define nl "\n"
#define pb push_back

int n, steps, rootX, rootY, homeX, homeY;

vector<pii> adj[800][800];
bool vis[800][800];
int dist[800][800];
bool visBee[800][800];
int distBee[800][800];
bool blocked[800][800];
bool blocked1[800][800];
vector<pii> hives;

void bfsBees() {
	queue<pii> bfsQueue;
	for (pii root : hives) {
		visBee[root.pA][root.pB] = true;
		bfsQueue.push(root);
		distBee[root.pA][root.pB] = 0;
	}
	while (!bfsQueue.empty()) {
		pii node = bfsQueue.front();
		bfsQueue.pop();
		for (pii neighbor : adj[node.pA][node.pB]) {
			if (!visBee[neighbor.pA][neighbor.pB] && !(neighbor.pA == homeX && neighbor.pB == homeY)) {
				visBee[neighbor.pA][neighbor.pB] = true;
				bfsQueue.push(neighbor);
				distBee[neighbor.pA][neighbor.pB] = distBee[node.pA][node.pB] + 1;
			}
		}
	}
}

bool bfs(int eatHoney) {
	FOR(i, 0, n) {
		FOR(j, 0, n) {
			vis[i][j] = false;
			visBee[i][j] = false;
			dist[i][j] = 1e9;
			distBee[i][j] = 1e9;
			blocked1[i][j] = false;
		}
	}
	queue<pii> bfsQueue;
	vis[rootX][rootY] = true;
	dist[rootX][rootY] = 0;
	bfsQueue.push(pii(rootX, rootY));
	bfsBees();
	while (!bfsQueue.empty()) {
		pii node = bfsQueue.front();
		bfsQueue.pop();
		for (pii neighbor : adj[node.pA][node.pB]) {
			if (!vis[neighbor.pA][neighbor.pB]) {
				vis[neighbor.pA][neighbor.pB] = true;
				bfsQueue.push(neighbor);
				dist[neighbor.pA][neighbor.pB] = dist[node.pA][node.pB] + 1;
			}
		}
	}
	FOR(i, 0, n) {
		FOR(j, 0, n) {
			if (((double)dist[i][j])/steps >= distBee[i][j] - eatHoney){
				blocked1[i][j] = true;
			}
		}
	}
	FOR(i, 0, n) {
		FOR(j, 0, n) {
			vis[i][j] = false;
			dist[i][j] = 1e9;
		}
	}
	bfsQueue = queue<pii>();
	vis[rootX][rootY] = true;
	bfsQueue.push(pii(rootX, rootY));
	dist[rootX][rootY] = 0;
	while (!bfsQueue.empty()) {
		pii node = bfsQueue.front();
		bfsQueue.pop();
		if (blocked1[node.pA][node.pB]) {
			continue;
		}
		for (pii neighbor : adj[node.pA][node.pB]) {
			if (!vis[neighbor.pA][neighbor.pB] && !blocked1[neighbor.pA][neighbor.pB]) {
				vis[neighbor.pA][neighbor.pB] = true;
				bfsQueue.push(neighbor);
				dist[neighbor.pA][neighbor.pB] = dist[node.pA][node.pB] + 1;
			}
		}
	}
	return (dist[homeX][homeY] != 1e9);
}

void gridAdj() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!blocked[i][j]) {
				if (i > 0 && !blocked[i - 1][j]) {
					adj[i][j].pb(pii(i - 1, j));
				}
				if (i < n - 1 && !blocked[i + 1][j]) {
					adj[i][j].pb(pii(i + 1, j));
				}
				if (j > 0 && !blocked[i][j - 1]) {
					adj[i][j].pb(pii(i, j - 1));
				}
				if (j < n - 1 && !blocked[i][j + 1]) {
					adj[i][j].pb(pii(i, j + 1));
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> steps;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		FOR(j, 0, n) {
			if (s[j] == 'T') {
				blocked[i][j] = true;
			} else if (s[j] == 'M') {
				rootX = i;
				rootY = j;
			} else if (s[j] == 'D') {
				homeX = i;
				homeY = j;
			} else if (s[j] == 'H') {
				hives.pb(pii(i, j));
			}
		}
	}
	gridAdj();
	int l = 0;
	int r = 1e6;
	int ans = l - 1;
	while (l <= r) {
		ll mid = (r + l) / 2;
		if (bfs(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	cout << ans << nl;
}

Subtask #1

46.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	15436 KB	Output is correct
2	Correct	10 ms	15344 KB	Output is correct
3	Correct	8 ms	15376 KB	Output is correct
4	Correct	8 ms	15348 KB	Output is correct
5	Correct	8 ms	15436 KB	Output is correct
6	Correct	8 ms	15348 KB	Output is correct
7	Execution timed out	1064 ms	53556 KB	Time limit exceeded
8	Correct	8 ms	15544 KB	Output is correct
9	Correct	8 ms	15436 KB	Output is correct
10	Correct	8 ms	15468 KB	Output is correct
11	Correct	9 ms	15476 KB	Output is correct
12	Correct	12 ms	15988 KB	Output is correct
13	Correct	12 ms	15820 KB	Output is correct
14	Correct	12 ms	15988 KB	Output is correct
15	Correct	8 ms	15552 KB	Output is correct
16	Correct	8 ms	15564 KB	Output is correct
17	Correct	8 ms	15564 KB	Output is correct
18	Correct	8 ms	15564 KB	Output is correct
19	Correct	8 ms	15564 KB	Output is correct
20	Correct	9 ms	15612 KB	Output is correct
21	Correct	8 ms	15680 KB	Output is correct
22	Correct	9 ms	15776 KB	Output is correct
23	Correct	9 ms	15820 KB	Output is correct
24	Correct	9 ms	15820 KB	Output is correct
25	Correct	10 ms	15964 KB	Output is correct
26	Correct	11 ms	15988 KB	Output is correct
27	Correct	12 ms	15948 KB	Output is correct
28	Correct	10 ms	15996 KB	Output is correct
29	Correct	12 ms	16076 KB	Output is correct
30	Correct	11 ms	15992 KB	Output is correct
31	Correct	10 ms	16124 KB	Output is correct
32	Correct	11 ms	16076 KB	Output is correct
33	Correct	65 ms	20684 KB	Output is correct
34	Correct	74 ms	20680 KB	Output is correct
35	Incorrect	322 ms	22528 KB	Output isn't correct
36	Correct	87 ms	21864 KB	Output is correct
37	Correct	87 ms	21736 KB	Output is correct
38	Incorrect	457 ms	24260 KB	Output isn't correct
39	Correct	117 ms	22968 KB	Output is correct
40	Correct	107 ms	22860 KB	Output is correct
41	Incorrect	649 ms	26104 KB	Output isn't correct
42	Correct	126 ms	24232 KB	Output is correct
43	Correct	132 ms	24224 KB	Output is correct
44	Incorrect	855 ms	28092 KB	Output isn't correct
45	Correct	156 ms	25500 KB	Output is correct
46	Correct	156 ms	25592 KB	Output is correct
47	Execution timed out	1066 ms	30248 KB	Time limit exceeded
48	Correct	184 ms	27008 KB	Output is correct
49	Correct	183 ms	26912 KB	Output is correct
50	Execution timed out	1067 ms	32500 KB	Time limit exceeded
51	Correct	204 ms	28520 KB	Output is correct
52	Correct	213 ms	28460 KB	Output is correct
53	Execution timed out	1084 ms	35060 KB	Time limit exceeded
54	Correct	249 ms	30148 KB	Output is correct
55	Correct	251 ms	30092 KB	Output is correct
56	Execution timed out	1096 ms	37620 KB	Time limit exceeded
57	Correct	289 ms	31720 KB	Output is correct
58	Correct	281 ms	31780 KB	Output is correct
59	Execution timed out	1041 ms	40392 KB	Time limit exceeded
60	Correct	315 ms	33528 KB	Output is correct
61	Correct	314 ms	33512 KB	Output is correct
62	Execution timed out	1018 ms	43396 KB	Time limit exceeded
63	Execution timed out	1089 ms	36932 KB	Time limit exceeded
64	Execution timed out	1075 ms	36952 KB	Time limit exceeded
65	Execution timed out	1071 ms	36988 KB	Time limit exceeded
66	Execution timed out	1062 ms	36932 KB	Time limit exceeded
67	Execution timed out	1077 ms	37012 KB	Time limit exceeded
68	Execution timed out	1090 ms	36932 KB	Time limit exceeded
69	Execution timed out	1053 ms	37060 KB	Time limit exceeded
70	Execution timed out	1091 ms	37052 KB	Time limit exceeded
71	Execution timed out	1046 ms	37060 KB	Time limit exceeded
72	Execution timed out	1067 ms	37064 KB	Time limit exceeded
73	Execution timed out	1062 ms	53572 KB	Time limit exceeded
74	Execution timed out	1059 ms	53528 KB	Time limit exceeded
75	Execution timed out	1063 ms	53572 KB	Time limit exceeded
76	Execution timed out	1036 ms	53456 KB	Time limit exceeded
77	Execution timed out	1082 ms	53500 KB	Time limit exceeded
78	Execution timed out	1029 ms	53524 KB	Time limit exceeded
79	Execution timed out	1074 ms	53636 KB	Time limit exceeded
80	Execution timed out	1076 ms	53444 KB	Time limit exceeded
81	Execution timed out	1074 ms	53468 KB	Time limit exceeded
82	Execution timed out	1086 ms	53548 KB	Time limit exceeded
83	Execution timed out	1074 ms	53336 KB	Time limit exceeded
84	Execution timed out	1065 ms	53404 KB	Time limit exceeded
85	Execution timed out	1083 ms	53408 KB	Time limit exceeded
86	Execution timed out	1081 ms	53344 KB	Time limit exceeded
87	Execution timed out	1079 ms	53380 KB	Time limit exceeded
88	Execution timed out	1057 ms	53492 KB	Time limit exceeded
89	Execution timed out	1079 ms	53316 KB	Time limit exceeded
90	Execution timed out	1059 ms	53320 KB	Time limit exceeded
91	Execution timed out	1033 ms	53488 KB	Time limit exceeded
92	Execution timed out	1068 ms	53468 KB	Time limit exceeded