oj.uz

Submission #599792

# Submission time Handle Problem Language Result Execution time Memory
599792 2022-07-19T23:10:26 Z alexz1205 Mecho (IOI09_mecho) C++14
2 / 100
 1000 ms 3860 KB 
#include <iostream>
#include <vector>
using namespace std;

int n, s, dist[802][802];
pair<int, int> beg, home;
vector<pair<int, int> > hives;

void setup(){
	cin >> n >> s;
	for (int x = 1; x <= n; x ++){
		for (int y = 1; y <= n; y ++){
			dist[x][y] = -1;
			char c;
			cin >> c;
			switch (c){
				case 'T':
					dist[x][y] = 0;
					break;
				case 'G':
					break;
				case 'M':
					beg = make_pair(x, y);
					break;
				case 'D':
					home = make_pair(x, y);
					break;
				case 'H':
					dist[x][y] = 0;
					hives.push_back(make_pair(x, y));
					break;
			}
		}
	}
	for (int x = 0; x <= n+1; x ++){
		dist[x][0] = dist[0][x] = dist[n+1][x] = dist[x][n+1] = 0;
	}
}

void calc(){
	vector<pair<int, int> > que = hives;
	while (!que.empty()){
		int i = que.front().first, j = que.front().second;
		que.erase(que.begin());
		if (dist[i-1][j] == -1){
			dist[i-1][j] = dist[i][j] + s;
			que.push_back(make_pair(i-1, j));
		}
		if (dist[i+1][j] == -1){
			dist[i+1][j] = dist[i][j] + s;
			que.push_back(make_pair(i+1, j));
		}
		if (dist[i][j-1] == -1){
			dist[i][j-1] = dist[i][j] + s;
			que.push_back(make_pair(i, j-1));
		}
		if (dist[i][j+1] == -1){
			dist[i][j+1] = dist[i][j] + s;
			que.push_back(make_pair(i, j+1));
		}
	}
}

bool pos(int mid){
	vector<pair<pair<int, int>, int> > que;
	que.push_back(make_pair(beg, mid));
	while (!que.empty()){
		int i = que.front().first.first, j = que.front().first.second;
		int d = que.front().second;
		que.erase(que.begin());
		if (i == home.first && j == home.second){
			return true;
		}
		if (dist[i-1][j] > d){
			que.push_back(make_pair(make_pair(i-1, j), d+1));
		}
		if (dist[i+1][j] > d){
			que.push_back(make_pair(make_pair(i+1, j), d+1));
		}
		if (dist[i][j-1] > d){
			que.push_back(make_pair(make_pair(i, j-1), d+1));
		}
		if (dist[i][j+1] > d){
			que.push_back(make_pair(make_pair(i, j+1), d+1));
		}
	}
	return false;
}

int main() {
	setup();
	calc();
	int lo = 0, hi = dist[beg.first][beg.second]/s+1;
	while (lo <= hi){
		int mid = lo + (hi-lo+1)/2;
		if (pos(s*mid)){
			lo = mid+1;
		}else {
			hi = mid-1;
		}
	}
	cout << lo-1 << endl;
	return 0;
}

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 1 ms 340 KB Output is correct
6 Execution timed out 1086 ms 1440 KB Time limit exceeded
7 Execution timed out 1091 ms 3112 KB Time limit exceeded
8 Incorrect 2 ms 340 KB Output isn't correct
9 Execution timed out 1087 ms 2004 KB Time limit exceeded
10 Execution timed out 1091 ms 2120 KB Time limit exceeded
11 Execution timed out 1092 ms 1320 KB Time limit exceeded
12 Incorrect 1 ms 516 KB Output isn't correct
13 Execution timed out 1089 ms 2144 KB Time limit exceeded
14 Execution timed out 1085 ms 2204 KB Time limit exceeded
15 Incorrect 0 ms 340 KB Output isn't correct
16 Execution timed out 1095 ms 1224 KB Time limit exceeded
17 Incorrect 0 ms 340 KB Output isn't correct
18 Execution timed out 1096 ms 1192 KB Time limit exceeded
19 Incorrect 1 ms 340 KB Output isn't correct
20 Execution timed out 1085 ms 1204 KB Time limit exceeded
21 Incorrect 0 ms 340 KB Output isn't correct
22 Execution timed out 1081 ms 1336 KB Time limit exceeded
23 Incorrect 1 ms 340 KB Output isn't correct
24 Execution timed out 1093 ms 1272 KB Time limit exceeded
25 Incorrect 1 ms 468 KB Output isn't correct
26 Execution timed out 1085 ms 1308 KB Time limit exceeded
27 Incorrect 1 ms 468 KB Output isn't correct
28 Execution timed out 1095 ms 1340 KB Time limit exceeded
29 Incorrect 1 ms 468 KB Output isn't correct
30 Execution timed out 1097 ms 1420 KB Time limit exceeded
31 Incorrect 1 ms 468 KB Output isn't correct
32 Execution timed out 1087 ms 1348 KB Time limit exceeded
33 Incorrect 8 ms 1364 KB Output isn't correct
34 Execution timed out 1086 ms 2236 KB Time limit exceeded
35 Execution timed out 1090 ms 2456 KB Time limit exceeded
36 Incorrect 13 ms 1492 KB Output isn't correct
37 Execution timed out 1098 ms 2504 KB Time limit exceeded
38 Execution timed out 1088 ms 2456 KB Time limit exceeded
39 Incorrect 13 ms 1620 KB Output isn't correct
40 Execution timed out 1091 ms 2564 KB Time limit exceeded
41 Execution timed out 1068 ms 2536 KB Time limit exceeded
42 Incorrect 16 ms 1876 KB Output isn't correct
43 Execution timed out 1082 ms 2820 KB Time limit exceeded
44 Execution timed out 1085 ms 2788 KB Time limit exceeded
45 Incorrect 19 ms 2004 KB Output isn't correct
46 Execution timed out 1095 ms 2936 KB Time limit exceeded
47 Execution timed out 1097 ms 2848 KB Time limit exceeded
48 Incorrect 22 ms 2124 KB Output isn't correct
49 Execution timed out 1090 ms 3208 KB Time limit exceeded
50 Execution timed out 1091 ms 3044 KB Time limit exceeded
51 Incorrect 26 ms 2232 KB Output isn't correct
52 Execution timed out 1093 ms 3192 KB Time limit exceeded
53 Execution timed out 1091 ms 3272 KB Time limit exceeded
54 Incorrect 31 ms 2392 KB Output isn't correct
55 Execution timed out 1091 ms 3424 KB Time limit exceeded
56 Execution timed out 1094 ms 3572 KB Time limit exceeded
57 Incorrect 35 ms 2552 KB Output isn't correct
58 Execution timed out 1094 ms 3580 KB Time limit exceeded
59 Execution timed out 1089 ms 3556 KB Time limit exceeded
60 Incorrect 41 ms 2776 KB Output isn't correct
61 Execution timed out 1088 ms 3692 KB Time limit exceeded
62 Execution timed out 1096 ms 3588 KB Time limit exceeded
63 Execution timed out 1063 ms 3660 KB Time limit exceeded
64 Execution timed out 1058 ms 3688 KB Time limit exceeded
65 Execution timed out 1087 ms 3860 KB Time limit exceeded
66 Execution timed out 1097 ms 3632 KB Time limit exceeded
67 Execution timed out 1097 ms 3680 KB Time limit exceeded
68 Execution timed out 1095 ms 3784 KB Time limit exceeded
69 Execution timed out 1091 ms 3628 KB Time limit exceeded
70 Execution timed out 1089 ms 3828 KB Time limit exceeded
71 Execution timed out 1074 ms 3756 KB Time limit exceeded
72 Execution timed out 1091 ms 3596 KB Time limit exceeded
73 Execution timed out 1089 ms 3300 KB Time limit exceeded
74 Execution timed out 1090 ms 3268 KB Time limit exceeded
75 Execution timed out 1073 ms 3244 KB Time limit exceeded
76 Execution timed out 1093 ms 3368 KB Time limit exceeded
77 Execution timed out 1077 ms 3272 KB Time limit exceeded
78 Execution timed out 1091 ms 3252 KB Time limit exceeded
79 Execution timed out 1079 ms 3284 KB Time limit exceeded
80 Execution timed out 1093 ms 3200 KB Time limit exceeded
81 Execution timed out 1098 ms 3196 KB Time limit exceeded
82 Execution timed out 1085 ms 3276 KB Time limit exceeded
83 Execution timed out 1093 ms 3316 KB Time limit exceeded
84 Execution timed out 1084 ms 3484 KB Time limit exceeded
85 Execution timed out 1092 ms 3496 KB Time limit exceeded
86 Execution timed out 1094 ms 3288 KB Time limit exceeded
87 Execution timed out 1089 ms 3224 KB Time limit exceeded
88 Execution timed out 1089 ms 3080 KB Time limit exceeded
89 Execution timed out 1098 ms 3096 KB Time limit exceeded
90 Execution timed out 1092 ms 3196 KB Time limit exceeded
91 Execution timed out 1089 ms 3224 KB Time limit exceeded
92 Execution timed out 1082 ms 3116 KB Time limit exceeded