oj.uz

Submission #816998

# Submission time Handle Problem Language Result Execution time Memory
816998 2023-08-09T08:18:39 Z Asamai Mecho (IOI09_mecho) C++17
56 / 100
 370 ms 8628 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});
				if (time + 1 < dist[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});
					if (time + 1 < dist[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(2);
	// 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
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Correct 180 ms 5068 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 484 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 488 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 488 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 616 KB Output is correct
28 Correct 1 ms 616 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 680 KB Output is correct
33 Correct 5 ms 1996 KB Output is correct
34 Correct 11 ms 2000 KB Output is correct
35 Incorrect 50 ms 2388 KB Output isn't correct
36 Correct 6 ms 2160 KB Output is correct
37 Correct 12 ms 2160 KB Output is correct
38 Incorrect 59 ms 2772 KB Output isn't correct
39 Correct 11 ms 2516 KB Output is correct
40 Correct 11 ms 2516 KB Output is correct
41 Incorrect 108 ms 3148 KB Output isn't correct
42 Correct 8 ms 2836 KB Output is correct
43 Correct 13 ms 2772 KB Output is correct
44 Incorrect 117 ms 3656 KB Output isn't correct
45 Correct 15 ms 3140 KB Output is correct
46 Correct 16 ms 3164 KB Output is correct
47 Incorrect 177 ms 4116 KB Output isn't correct
48 Correct 12 ms 3460 KB Output is correct
49 Correct 18 ms 3412 KB Output is correct
50 Incorrect 157 ms 4596 KB Output isn't correct
51 Correct 13 ms 3748 KB Output is correct
52 Correct 27 ms 3812 KB Output is correct
53 Incorrect 201 ms 5112 KB Output isn't correct
54 Correct 17 ms 4112 KB Output is correct
55 Correct 24 ms 4080 KB Output is correct
56 Incorrect 259 ms 5672 KB Output isn't correct
57 Correct 17 ms 4424 KB Output is correct
58 Correct 32 ms 4456 KB Output is correct
59 Incorrect 303 ms 6360 KB Output isn't correct
60 Correct 23 ms 4716 KB Output is correct
61 Correct 30 ms 4820 KB Output is correct
62 Incorrect 311 ms 6868 KB Output isn't correct
63 Correct 189 ms 4676 KB Output is correct
64 Correct 370 ms 8628 KB Output is correct
65 Incorrect 334 ms 4796 KB Output isn't correct
66 Correct 222 ms 4788 KB Output is correct
67 Correct 189 ms 4788 KB Output is correct
68 Incorrect 63 ms 4824 KB Output isn't correct
69 Correct 50 ms 5056 KB Output is correct
70 Incorrect 64 ms 4808 KB Output isn't correct
71 Incorrect 33 ms 4700 KB Output isn't correct
72 Correct 29 ms 4976 KB Output is correct
73 Correct 51 ms 4948 KB Output is correct
74 Correct 118 ms 5964 KB Output is correct
75 Incorrect 125 ms 5060 KB Output isn't correct
76 Incorrect 125 ms 5068 KB Output isn't correct
77 Incorrect 131 ms 5088 KB Output isn't correct
78 Correct 133 ms 5024 KB Output is correct
79 Correct 104 ms 6404 KB Output is correct
80 Correct 115 ms 5028 KB Output is correct
81 Incorrect 135 ms 5028 KB Output isn't correct
82 Correct 109 ms 5020 KB Output is correct
83 Correct 158 ms 4988 KB Output is correct
84 Correct 129 ms 6492 KB Output is correct
85 Correct 128 ms 4980 KB Output is correct
86 Correct 163 ms 4980 KB Output is correct
87 Correct 145 ms 5056 KB Output is correct
88 Correct 167 ms 4936 KB Output is correct
89 Correct 168 ms 6600 KB Output is correct
90 Correct 188 ms 5092 KB Output is correct
91 Correct 193 ms 5304 KB Output is correct
92 Correct 184 ms 4996 KB Output is correct