oj.uz

Submission #816070

# Submission time Handle Problem Language Result Execution time Memory
816070 2023-08-09T04:07:42 Z Asamai Mecho (IOI09_mecho) C++17
42 / 100
 359 ms 8476 KB 
#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 800 + 5;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int n, S;
string a[MAX_N];
pii s, t;
int dist[MAX_N][MAX_N];
bool ok[MAX_N][MAX_N];

bool inside(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= n;
}

bool check(int mid) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ok[i][j] = false;
		}
	}

	queue<pair<pii, int>> q;
	q.push({s, mid + 1});
	ok[s.fi][s.se] = true;
	while (!q.empty()) {
		int u = q.front().fi.fi;
		int v = q.front().fi.se;
		int time = q.front().se;

		q.pop();

		queue<pii> nxt_q;
		for (int k = 0; k < 4; k++) {
			int x = u + dx[k];
			int y = v + dy[k];

			if (inside(x, y) && (a[x][y] == 'G' || a[x][y] == 'D') && !ok[x][y] && dist[x][y] > time) {
				ok[x][y] = true;
				nxt_q.push({x, y});
				q.push({{x, y}, time + 1});
			}
		}

		while (!nxt_q.empty()) {
			int nxt_u = nxt_q.front().fi;
			int nxt_v = nxt_q.front().se;

			nxt_q.pop();

			if (abs(nxt_u - u) + abs(nxt_v - v) == S) {
				continue;
			}

			for (int k = 0; k < 4; k++) {
				int x = nxt_u + dx[k];
				int y = nxt_v + dy[k];
				if (inside(x, y) && (a[x][y] == 'G' || a[x][y] == 'D') && !ok[x][y] && dist[x][y] > time) {
					ok[x][y] = true;
					nxt_q.push({x, y});
					q.push({{x, y}, time + 1});
				}
			}
		}

	}

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 1; j <= n; j++) {
	// 		cout << ok[i][j] << " ";
	// 	}
	// 	cout << '\n';
	// }

	return ok[t.fi][t.se];
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	queue<pii> q;
	cin >> n >> S;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] = ' ' + a[i];
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == 'M') {
				s = {i, j};
			}
			if (a[i][j] == 'D') {
				t = {i, j};
			}
			if (a[i][j] == 'H') {
				q.push({i, j});
				dist[i][j] = 1;
			}
		}
	}
	dist[t.fi][t.se] = 1e9;

	while (!q.empty()) {
		int u = q.front().fi;
		int v = q.front().se;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int x = u + dx[k];
			int y = v + dy[k];
			if (inside(x, y) && (a[x][y] == 'G' || a[x][y] == 'M') && !dist[x][y]) {
				dist[x][y] = dist[u][v] + 1;
				q.push({x, y});
			}
		}
	}

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 1; j <= n; j++) {
	// 		cout << dist[i][j] << " ";
	// 	}
	// 	cout << '\n';
	// }

	// cout << check(3);
	// return 0;

	int low = 0, high = dist[s.fi][s.se] - 2;
	int ans = -1;
	while (low <= high) {
		int mid = (low + high) >> 1;
		if (check(mid)) {
			ans = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}

	cout << ans;

	return 0;
}

/*


*/

Subtask #1
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 360 KB Output isn't correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 0 ms 352 KB Output isn't correct
7 Correct 245 ms 4772 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Correct 1 ms 356 KB Output is correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 468 KB Output isn't correct
20 Correct 1 ms 468 KB Output is correct
21 Incorrect 1 ms 468 KB Output isn't correct
22 Correct 1 ms 484 KB Output is correct
23 Incorrect 1 ms 468 KB Output isn't correct
24 Correct 1 ms 468 KB Output is correct
25 Incorrect 1 ms 596 KB Output isn't correct
26 Correct 1 ms 616 KB Output is correct
27 Incorrect 1 ms 620 KB Output isn't correct
28 Correct 2 ms 596 KB Output is correct
29 Incorrect 1 ms 596 KB Output isn't correct
30 Correct 2 ms 596 KB Output is correct
31 Incorrect 1 ms 596 KB Output isn't correct
32 Correct 1 ms 596 KB Output is correct
33 Incorrect 5 ms 1940 KB Output isn't correct
34 Correct 7 ms 1996 KB Output is correct
35 Incorrect 54 ms 2360 KB Output isn't correct
36 Incorrect 6 ms 2236 KB Output isn't correct
37 Correct 14 ms 2260 KB Output is correct
38 Incorrect 62 ms 2784 KB Output isn't correct
39 Incorrect 7 ms 2516 KB Output isn't correct
40 Correct 11 ms 2564 KB Output is correct
41 Incorrect 125 ms 3180 KB Output isn't correct
42 Incorrect 12 ms 2804 KB Output isn't correct
43 Correct 13 ms 2864 KB Output is correct
44 Incorrect 115 ms 3644 KB Output isn't correct
45 Incorrect 12 ms 3104 KB Output isn't correct
46 Correct 19 ms 3076 KB Output is correct
47 Incorrect 144 ms 4112 KB Output isn't correct
48 Incorrect 14 ms 3464 KB Output isn't correct
49 Correct 21 ms 3480 KB Output is correct
50 Incorrect 182 ms 4672 KB Output isn't correct
51 Incorrect 15 ms 3660 KB Output isn't correct
52 Correct 26 ms 3668 KB Output is correct
53 Incorrect 208 ms 5048 KB Output isn't correct
54 Incorrect 19 ms 3948 KB Output isn't correct
55 Correct 29 ms 4024 KB Output is correct
56 Incorrect 260 ms 5612 KB Output isn't correct
57 Incorrect 20 ms 4188 KB Output isn't correct
58 Correct 27 ms 4292 KB Output is correct
59 Incorrect 303 ms 6112 KB Output isn't correct
60 Incorrect 26 ms 4532 KB Output isn't correct
61 Correct 32 ms 4524 KB Output is correct
62 Incorrect 316 ms 6624 KB Output isn't correct
63 Correct 180 ms 4540 KB Output is correct
64 Correct 359 ms 8476 KB Output is correct
65 Incorrect 353 ms 4548 KB Output isn't correct
66 Incorrect 213 ms 4544 KB Output isn't correct
67 Correct 186 ms 4548 KB Output is correct
68 Incorrect 77 ms 4576 KB Output isn't correct
69 Correct 51 ms 4792 KB Output is correct
70 Incorrect 48 ms 4460 KB Output isn't correct
71 Incorrect 33 ms 4472 KB Output isn't correct
72 Correct 28 ms 4728 KB Output is correct
73 Correct 50 ms 4696 KB Output is correct
74 Correct 116 ms 5696 KB Output is correct
75 Incorrect 127 ms 4812 KB Output isn't correct
76 Incorrect 110 ms 4832 KB Output isn't correct
77 Incorrect 121 ms 4684 KB Output isn't correct
78 Correct 140 ms 4836 KB Output is correct
79 Correct 101 ms 6132 KB Output is correct
80 Correct 108 ms 4784 KB Output is correct
81 Correct 119 ms 4788 KB Output is correct
82 Correct 112 ms 4668 KB Output is correct
83 Correct 170 ms 4744 KB Output is correct
84 Correct 125 ms 6228 KB Output is correct
85 Correct 122 ms 4740 KB Output is correct
86 Correct 156 ms 4748 KB Output is correct
87 Correct 131 ms 4832 KB Output is correct
88 Correct 161 ms 4684 KB Output is correct
89 Correct 169 ms 6376 KB Output is correct
90 Correct 175 ms 4820 KB Output is correct
91 Correct 167 ms 5072 KB Output is correct
92 Correct 165 ms 4748 KB Output is correct