답안 #817207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817207	2023-08-09T10:36:06 Z	Asamai	Mecho (IOI09_mecho)	C++17	40 / 100	139 ms	5076 KB

mecho

#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 * S});
	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();

		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;
				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;
			}
		}
	}

	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++) {
			dist[i][j]--;
			dist[i][j] *= S;
		}
	}
	dist[t.fi][t.se] = 1e9;

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

	// cout << check(4);
	// 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

40.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	340 KB	Output isn't correct
2	Incorrect	0 ms	340 KB	Output isn't correct
3	Correct	0 ms	356 KB	Output is correct
4	Incorrect	0 ms	340 KB	Output isn't correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	356 KB	Output is correct
7	Correct	77 ms	4900 KB	Output is correct
8	Incorrect	0 ms	356 KB	Output isn't correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Incorrect	1 ms	484 KB	Output isn't correct
13	Incorrect	1 ms	468 KB	Output isn't correct
14	Correct	1 ms	596 KB	Output is correct
15	Incorrect	1 ms	340 KB	Output isn't correct
16	Correct	1 ms	340 KB	Output is correct
17	Incorrect	1 ms	340 KB	Output isn't correct
18	Correct	1 ms	468 KB	Output is correct
19	Incorrect	1 ms	484 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	468 KB	Output is correct
23	Incorrect	1 ms	468 KB	Output isn't correct
24	Correct	1 ms	480 KB	Output is correct
25	Incorrect	1 ms	484 KB	Output isn't correct
26	Correct	1 ms	484 KB	Output is correct
27	Incorrect	1 ms	596 KB	Output isn't correct
28	Correct	1 ms	616 KB	Output is correct
29	Incorrect	1 ms	596 KB	Output isn't correct
30	Correct	1 ms	616 KB	Output is correct
31	Incorrect	1 ms	612 KB	Output isn't correct
32	Correct	1 ms	644 KB	Output is correct
33	Incorrect	4 ms	1876 KB	Output isn't correct
34	Correct	3 ms	1876 KB	Output is correct
35	Correct	15 ms	1876 KB	Output is correct
36	Incorrect	4 ms	2260 KB	Output isn't correct
37	Correct	4 ms	2260 KB	Output is correct
38	Correct	25 ms	2260 KB	Output is correct
39	Incorrect	5 ms	2516 KB	Output isn't correct
40	Correct	4 ms	2528 KB	Output is correct
41	Correct	28 ms	2516 KB	Output is correct
42	Incorrect	6 ms	2772 KB	Output isn't correct
43	Correct	5 ms	2800 KB	Output is correct
44	Correct	35 ms	2768 KB	Output is correct
45	Incorrect	7 ms	3120 KB	Output isn't correct
46	Incorrect	14 ms	3028 KB	Output isn't correct
47	Correct	38 ms	3028 KB	Output is correct
48	Incorrect	8 ms	3480 KB	Output isn't correct
49	Incorrect	11 ms	3464 KB	Output isn't correct
50	Correct	56 ms	3460 KB	Output is correct
51	Incorrect	9 ms	3668 KB	Output isn't correct
52	Incorrect	20 ms	3728 KB	Output isn't correct
53	Correct	58 ms	3776 KB	Output is correct
54	Incorrect	10 ms	4076 KB	Output isn't correct
55	Incorrect	34 ms	4108 KB	Output isn't correct
56	Correct	94 ms	4108 KB	Output is correct
57	Incorrect	14 ms	4344 KB	Output isn't correct
58	Incorrect	21 ms	4400 KB	Output isn't correct
59	Correct	88 ms	4444 KB	Output is correct
60	Incorrect	13 ms	4692 KB	Output isn't correct
61	Incorrect	30 ms	4692 KB	Output isn't correct
62	Correct	92 ms	4812 KB	Output is correct
63	Correct	79 ms	4784 KB	Output is correct
64	Correct	139 ms	4788 KB	Output is correct
65	Correct	130 ms	4808 KB	Output is correct
66	Incorrect	90 ms	4780 KB	Output isn't correct
67	Correct	86 ms	4764 KB	Output is correct
68	Correct	36 ms	4696 KB	Output is correct
69	Correct	29 ms	4712 KB	Output is correct
70	Correct	29 ms	4812 KB	Output is correct
71	Correct	32 ms	4696 KB	Output is correct
72	Incorrect	22 ms	4704 KB	Output isn't correct
73	Incorrect	27 ms	4960 KB	Output isn't correct
74	Correct	37 ms	5060 KB	Output is correct
75	Correct	48 ms	5060 KB	Output is correct
76	Correct	47 ms	5068 KB	Output is correct
77	Correct	48 ms	5076 KB	Output is correct
78	Correct	63 ms	5028 KB	Output is correct
79	Correct	40 ms	4984 KB	Output is correct
80	Correct	45 ms	5052 KB	Output is correct
81	Correct	50 ms	5032 KB	Output is correct
82	Correct	45 ms	5040 KB	Output is correct
83	Correct	57 ms	4872 KB	Output is correct
84	Correct	53 ms	4988 KB	Output is correct
85	Correct	61 ms	4988 KB	Output is correct
86	Correct	57 ms	4996 KB	Output is correct
87	Correct	59 ms	4992 KB	Output is correct
88	Correct	58 ms	4936 KB	Output is correct
89	Correct	57 ms	4836 KB	Output is correct
90	Correct	74 ms	4936 KB	Output is correct
91	Correct	68 ms	4936 KB	Output is correct
92	Correct	59 ms	4944 KB	Output is correct