oj.uz

답안 #817552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817552 2023-08-09T13:32:32 Z Asamai Mecho (IOI09_mecho) C++17
43 / 100
 134 ms 5076 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 * 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;
 
	int low = 0, high = dist[s.fi][s.se] - 1;
	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
43.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 Incorrect 0 ms 352 KB Output isn't correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 65 ms 4896 KB Output is correct
8 Incorrect 1 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 0 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is 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 352 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 468 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 480 KB Output isn't correct
26 Correct 1 ms 596 KB Output is correct
27 Incorrect 1 ms 596 KB Output isn't correct
28 Correct 1 ms 612 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 596 KB Output isn't correct
32 Correct 1 ms 612 KB Output is correct
33 Incorrect 4 ms 1924 KB Output isn't correct
34 Correct 3 ms 1876 KB Output is correct
35 Correct 15 ms 2000 KB Output is correct
36 Incorrect 4 ms 2260 KB Output isn't correct
37 Correct 3 ms 2156 KB Output is correct
38 Correct 20 ms 2260 KB Output is correct
39 Incorrect 5 ms 2516 KB Output isn't correct
40 Correct 4 ms 2544 KB Output is correct
41 Correct 27 ms 2516 KB Output is correct
42 Incorrect 7 ms 2772 KB Output isn't correct
43 Correct 6 ms 2772 KB Output is correct
44 Correct 33 ms 2772 KB Output is correct
45 Incorrect 7 ms 3136 KB Output isn't correct
46 Incorrect 13 ms 3144 KB Output isn't correct
47 Correct 38 ms 3108 KB Output is correct
48 Incorrect 8 ms 3384 KB Output isn't correct
49 Incorrect 11 ms 3496 KB Output isn't correct
50 Correct 45 ms 3452 KB Output is correct
51 Incorrect 9 ms 3784 KB Output isn't correct
52 Incorrect 20 ms 3756 KB Output isn't correct
53 Correct 58 ms 3676 KB Output is correct
54 Incorrect 10 ms 4044 KB Output isn't correct
55 Incorrect 25 ms 4048 KB Output isn't correct
56 Correct 68 ms 4100 KB Output is correct
57 Incorrect 11 ms 4436 KB Output isn't correct
58 Incorrect 22 ms 4384 KB Output isn't correct
59 Correct 79 ms 4436 KB Output is correct
60 Incorrect 13 ms 4804 KB Output isn't correct
61 Incorrect 36 ms 4708 KB Output isn't correct
62 Correct 85 ms 4876 KB Output is correct
63 Correct 77 ms 4784 KB Output is correct
64 Correct 134 ms 4784 KB Output is correct
65 Correct 129 ms 4800 KB Output is correct
66 Incorrect 88 ms 4788 KB Output isn't correct
67 Correct 82 ms 4716 KB Output is correct
68 Correct 31 ms 4692 KB Output is correct
69 Correct 32 ms 4812 KB Output is correct
70 Correct 29 ms 4692 KB Output is correct
71 Correct 25 ms 4708 KB Output is correct
72 Incorrect 22 ms 4708 KB Output isn't correct
73 Incorrect 36 ms 5068 KB Output isn't correct
74 Correct 36 ms 5076 KB Output is correct
75 Correct 48 ms 5064 KB Output is correct
76 Correct 47 ms 5068 KB Output is correct
77 Correct 46 ms 5060 KB Output is correct
78 Correct 54 ms 5032 KB Output is correct
79 Correct 40 ms 5032 KB Output is correct
80 Correct 48 ms 5040 KB Output is correct
81 Correct 50 ms 5020 KB Output is correct
82 Correct 46 ms 5032 KB Output is correct
83 Correct 55 ms 4880 KB Output is correct
84 Correct 53 ms 5000 KB Output is correct
85 Correct 61 ms 4952 KB Output is correct
86 Correct 57 ms 4948 KB Output is correct
87 Correct 73 ms 5024 KB Output is correct
88 Correct 56 ms 4940 KB Output is correct
89 Correct 73 ms 4940 KB Output is correct
90 Correct 59 ms 4836 KB Output is correct
91 Correct 57 ms 4856 KB Output is correct
92 Correct 60 ms 4956 KB Output is correct