oj.uz

답안 #1066069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066069 2024-08-19T14:42:10 Z belgianbot Mecho (IOI09_mecho) C++17
48 / 100
 1000 ms 56404 KB 
#include <bits/stdc++.h>
#define se second
#define fi first

using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, S; cin >> N >> S;
	vector<string> grid(N);
	
	for (int i = 0; i < N; i++) {
		cin >> grid[i];
	}
	
	int start, end;
	vector<int> dist(N * N, INT_MAX);
	vector<vector<int>> adj(N * N);
	queue<pair<int,int>> hives;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == 'H') {
				hives.push({i * N + j, 1});
				dist[i * N + j] = 0;
			}
			else if (grid[i][j] == 'M') start = i * N + j;
			else if (grid[i][j] == 'D') end = i * N + j;
			if (grid[i][j] == 'H' || grid[i][j] == 'T') continue;
			if (i && (grid[i - 1][j] == 'D' || grid[i - 1][j] == 'H' || grid[i - 1][j] == 'M' || grid[i - 1][j] == 'G')) adj[i * N - N + j].push_back(i * N + j);
			if (j && (grid[i][j-1] == 'D' || grid[i][j-1] == 'H' || grid[i][j-1] == 'M' || grid[i][j-1] == 'G')) adj[i * N + j-1].push_back(i * N + j);
			if (i != N - 1 && (grid[i + 1][j] == 'D' || grid[i + 1][j] == 'H' || grid[i + 1][j] == 'M' || grid[i + 1][j] == 'G')) adj[i * N + N + j].push_back(i * N + j);
			if (j != N - 1 && (grid[i][j+1] == 'D' || grid[i][j+1] == 'H' || grid[i][j+1] == 'M' || grid[i][j+1] == 'G')) adj[i * N + j+1].push_back(i * N + j);
		}
	}
	
	
	while (!hives.empty()) {
		auto x = hives.front(); hives.pop();
		for (int y : adj[x.fi]) {
			if (dist[y] == INT_MAX && grid[y / N][y % N] != 'D'){
				hives.push({y, x.se + 1});
				dist[y] = x.se;
			}
		}
	}
	int maxi = 0;
	for (int x : adj[end]) maxi = max(maxi, dist[x] != INT_MAX ? dist[x] : 0);
	int l = 0, r = N * N / 2 + N;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		map<int, bool> pro;
		queue<pair<int,int>> q;
		q.push({mid * S, start});
		pro[start] = true;
		bool won = false;
		while (!q.empty() && !won){ //&& q.front().fi / S < maxi) {
			auto u = q.front(); q.pop();
			for (int x : adj[u.se]) {
				if (x == end) {won = true; break;}
				if (!pro[x] && (u.fi + 1) / S < dist[x]) {
					pro[x] = true;
					q.push({u.fi + 1, x});
				}
			}
		}

		if (won) l = mid + 1;
		else r = mid - 1;
	}
	
	cout << l - 1 << '\n';
	return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:60:5: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     if (x == end) {won = true; break;}
      |     ^~

Subtask #1
48.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 1098 ms 53964 KB Time limit exceeded
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 1 ms 604 KB Output isn't correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 456 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 456 KB Output is correct
26 Correct 0 ms 456 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 7 ms 5824 KB Output is correct
34 Correct 8 ms 5980 KB Output is correct
35 Correct 245 ms 11064 KB Output is correct
36 Correct 9 ms 7516 KB Output is correct
37 Correct 8 ms 7704 KB Output is correct
38 Correct 316 ms 14424 KB Output is correct
39 Correct 10 ms 9564 KB Output is correct
40 Correct 10 ms 9504 KB Output is correct
41 Correct 490 ms 18212 KB Output is correct
42 Correct 14 ms 11612 KB Output is correct
43 Correct 14 ms 11612 KB Output is correct
44 Correct 735 ms 22220 KB Output is correct
45 Correct 16 ms 13912 KB Output is correct
46 Correct 15 ms 14184 KB Output is correct
47 Correct 895 ms 26796 KB Output is correct
48 Correct 19 ms 16732 KB Output is correct
49 Correct 18 ms 16732 KB Output is correct
50 Execution timed out 1098 ms 31916 KB Time limit exceeded
51 Correct 23 ms 19548 KB Output is correct
52 Correct 22 ms 19404 KB Output is correct
53 Execution timed out 1066 ms 37516 KB Time limit exceeded
54 Correct 25 ms 22352 KB Output is correct
55 Correct 25 ms 22484 KB Output is correct
56 Execution timed out 1071 ms 43300 KB Time limit exceeded
57 Correct 32 ms 25680 KB Output is correct
58 Correct 32 ms 25944 KB Output is correct
59 Execution timed out 1068 ms 49860 KB Time limit exceeded
60 Correct 36 ms 29276 KB Output is correct
61 Correct 36 ms 29272 KB Output is correct
62 Execution timed out 1075 ms 56404 KB Time limit exceeded
63 Correct 825 ms 45908 KB Output is correct
64 Execution timed out 1020 ms 47684 KB Time limit exceeded
65 Execution timed out 1048 ms 47440 KB Time limit exceeded
66 Execution timed out 1043 ms 43856 KB Time limit exceeded
67 Correct 984 ms 40532 KB Output is correct
68 Correct 202 ms 35680 KB Output is correct
69 Correct 232 ms 35876 KB Output is correct
70 Correct 138 ms 34880 KB Output is correct
71 Correct 144 ms 34116 KB Output is correct
72 Incorrect 74 ms 31568 KB Output isn't correct
73 Incorrect 378 ms 51280 KB Output isn't correct
74 Correct 658 ms 47952 KB Output is correct
75 Execution timed out 1039 ms 48980 KB Time limit exceeded
76 Correct 838 ms 48452 KB Output is correct
77 Correct 794 ms 47444 KB Output is correct
78 Execution timed out 1036 ms 51792 KB Time limit exceeded
79 Correct 513 ms 46416 KB Output is correct
80 Correct 900 ms 47700 KB Output is correct
81 Execution timed out 1072 ms 49588 KB Time limit exceeded
82 Correct 855 ms 49268 KB Output is correct
83 Execution timed out 1042 ms 51792 KB Time limit exceeded
84 Execution timed out 1081 ms 50264 KB Time limit exceeded
85 Execution timed out 1014 ms 51280 KB Time limit exceeded
86 Execution timed out 1041 ms 51940 KB Time limit exceeded
87 Execution timed out 1055 ms 52052 KB Time limit exceeded
88 Execution timed out 1040 ms 52828 KB Time limit exceeded
89 Execution timed out 1081 ms 53076 KB Time limit exceeded
90 Execution timed out 1059 ms 53076 KB Time limit exceeded
91 Execution timed out 1012 ms 53668 KB Time limit exceeded
92 Execution timed out 1050 ms 52856 KB Time limit exceeded