oj.uz

Submission #516244

# Submission time Handle Problem Language Result Execution time Memory
516244 2022-01-20T19:05:06 Z Tizariox Mecho (IOI09_mecho) C++14
76 / 100
 527 ms 53032 KB 
#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;
			}
		}
	}
}

void bfsBear() {
	queue<pii> bfsQueue;
	vis[rootX][rootY] = true;
	dist[rootX][rootY] = 0;
	bfsQueue.push(pii(rootX, rootY));
	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;
			}
		}
	}
}

bool bfs(int eatHoney) {
	FOR(i, 0, n) {
		FOR(j, 0, n) {
			if (((double)dist[i][j])/steps >= max(distBee[i][j] - eatHoney, 0)){
				blocked1[i][j] = true;
			} else {
				blocked1[i][j] = false;
			}
			vis[i][j] = false;
		}
	}
	queue<pii> bfsQueue;
	vis[rootX][rootY] = true;
	bfsQueue.push(pii(rootX, rootY));
	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;
				if (neighbor.pA == homeX && neighbor.pB == homeY) {
					return true;
				}
				bfsQueue.push(neighbor);
			}
		}
	}
	return vis[homeX][homeY];
}

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() {
	// freopen("!.in", "r", stdin);
	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));
			}
		}
	}
	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;
		}
	}
	gridAdj();
	bfsBees();
	bfsBear();
	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
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15288 KB Output is correct
2 Correct 8 ms 15308 KB Output is correct
3 Correct 8 ms 15308 KB Output is correct
4 Correct 8 ms 15308 KB Output is correct
5 Correct 8 ms 15440 KB Output is correct
6 Correct 8 ms 15432 KB Output is correct
7 Correct 526 ms 52972 KB Output is correct
8 Correct 8 ms 15516 KB Output is correct
9 Correct 8 ms 15508 KB Output is correct
10 Correct 8 ms 15448 KB Output is correct
11 Correct 8 ms 15436 KB Output is correct
12 Correct 10 ms 15948 KB Output is correct
13 Correct 9 ms 15820 KB Output is correct
14 Correct 12 ms 16060 KB Output is correct
15 Correct 9 ms 15556 KB Output is correct
16 Correct 10 ms 15436 KB Output is correct
17 Correct 9 ms 15564 KB Output is correct
18 Correct 10 ms 15564 KB Output is correct
19 Correct 9 ms 15564 KB Output is correct
20 Correct 8 ms 15564 KB Output is correct
21 Correct 9 ms 15692 KB Output is correct
22 Correct 10 ms 15692 KB Output is correct
23 Correct 8 ms 15820 KB Output is correct
24 Correct 8 ms 15820 KB Output is correct
25 Correct 8 ms 15948 KB Output is correct
26 Correct 9 ms 15948 KB Output is correct
27 Correct 9 ms 15948 KB Output is correct
28 Correct 8 ms 15948 KB Output is correct
29 Correct 9 ms 16056 KB Output is correct
30 Correct 8 ms 16076 KB Output is correct
31 Correct 9 ms 16076 KB Output is correct
32 Correct 9 ms 16164 KB Output is correct
33 Correct 20 ms 20580 KB Output is correct
34 Correct 21 ms 20564 KB Output is correct
35 Incorrect 82 ms 22440 KB Output isn't correct
36 Correct 23 ms 21632 KB Output is correct
37 Correct 25 ms 21588 KB Output is correct
38 Incorrect 110 ms 24096 KB Output isn't correct
39 Correct 28 ms 22776 KB Output is correct
40 Correct 28 ms 22732 KB Output is correct
41 Incorrect 137 ms 25804 KB Output isn't correct
42 Correct 31 ms 23884 KB Output is correct
43 Correct 32 ms 23988 KB Output is correct
44 Incorrect 180 ms 27840 KB Output isn't correct
45 Correct 47 ms 25252 KB Output is correct
46 Correct 40 ms 25160 KB Output is correct
47 Incorrect 235 ms 29856 KB Output isn't correct
48 Correct 41 ms 26600 KB Output is correct
49 Correct 42 ms 26572 KB Output is correct
50 Incorrect 274 ms 32220 KB Output isn't correct
51 Correct 51 ms 27992 KB Output is correct
52 Correct 49 ms 28072 KB Output is correct
53 Incorrect 316 ms 34564 KB Output isn't correct
54 Correct 52 ms 29628 KB Output is correct
55 Correct 59 ms 29620 KB Output is correct
56 Incorrect 393 ms 37220 KB Output isn't correct
57 Correct 61 ms 31240 KB Output is correct
58 Correct 62 ms 31232 KB Output is correct
59 Incorrect 474 ms 39964 KB Output isn't correct
60 Correct 65 ms 32896 KB Output is correct
61 Correct 70 ms 32988 KB Output is correct
62 Incorrect 527 ms 42824 KB Output isn't correct
63 Correct 256 ms 36396 KB Output is correct
64 Correct 346 ms 36376 KB Output is correct
65 Correct 347 ms 36392 KB Output is correct
66 Correct 296 ms 36396 KB Output is correct
67 Correct 252 ms 36420 KB Output is correct
68 Correct 169 ms 36420 KB Output is correct
69 Correct 168 ms 36424 KB Output is correct
70 Correct 166 ms 36328 KB Output is correct
71 Correct 148 ms 36428 KB Output is correct
72 Correct 135 ms 36428 KB Output is correct
73 Correct 276 ms 52916 KB Output is correct
74 Correct 363 ms 53032 KB Output is correct
75 Correct 353 ms 52884 KB Output is correct
76 Correct 344 ms 53032 KB Output is correct
77 Correct 349 ms 52924 KB Output is correct
78 Correct 350 ms 52900 KB Output is correct
79 Correct 289 ms 52900 KB Output is correct
80 Correct 317 ms 52788 KB Output is correct
81 Correct 333 ms 52900 KB Output is correct
82 Correct 296 ms 52800 KB Output is correct
83 Correct 481 ms 52844 KB Output is correct
84 Correct 429 ms 52776 KB Output is correct
85 Correct 436 ms 52788 KB Output is correct
86 Correct 465 ms 52784 KB Output is correct
87 Correct 443 ms 52752 KB Output is correct
88 Correct 459 ms 52760 KB Output is correct
89 Correct 499 ms 52808 KB Output is correct
90 Correct 496 ms 52808 KB Output is correct
91 Correct 470 ms 52804 KB Output is correct
92 Correct 505 ms 52752 KB Output is correct