# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
245582 |
2020-07-06T20:08:38 Z |
tatyam |
Mecho (IOI09_mecho) |
C++17 |
|
272 ms |
6336 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 0x3fffffff;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
#define name2(a,b,c,...) c
#define rep1(b) for(int i = 0; i < b; i++)
#define rep2(i,b) for(int i = 0; i < b; i++)
#define rep(...) name2(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, s;
cin >> n >> s;
vector<string> a(n);
each(i, a) cin >> i;
vector<vector<int>> bee(n, vector<int>(n, INF));
queue<pii> q;
rep(n) rep(j, n) if(a[i][j] == 'H'){
bee[i][j] = 0;
q.emplace(i, j);
}
while(q.size()){
auto [x, y] = q.front();
q.pop();
rep(4){
int x2 = x + dx[i], y2 = y + dy[i];
if(x2 < 0 || y2 < 0 || x2 >= n || y2 >= n || a[x2][y2] != 'G' && a[x2][y2] != 'M') continue;
if(chmin(bee[x2][y2], bee[x][y] + 1)) q.emplace(x2, y2);
}
}
pii start, goal;
rep(n) rep(j, n) if(a[i][j] == 'M') start = {i, j};
rep(n) rep(j, n) if(a[i][j] == 'D') goal = {i, j};
auto check = [&](int v) -> bool {
if(bee[start.first][start.second] <= v) return false;
vector<vector<int>> m(n, vector<int>(n, INF));
m[start.first][start.second] = 0;
q.push(start);
while(q.size()){
auto [x, y] = q.front();
q.pop();
int next = m[x][y] + 1;
rep(4){
int x2 = x + dx[i], y2 = y + dy[i];
if(x2 < 0 || y2 < 0 || x2 >= n || y2 >= n || a[x2][y2] == 'T') continue;
if(next / s + v < bee[x2][y2] && chmin(m[x2][y2], next)) q.emplace(x2, y2);
}
}
return m[goal.first][goal.second] != INF;
};
int ok = -1, ng = n * n;
while(ng - ok > 1){
int cen = (ok + ng) / 2;
if(check(cen)) ok = cen;
else ng = cen;
}
cout << ok << endl;
}
Compilation message
mecho.cpp: In function 'int main()':
mecho.cpp:34:75: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(x2 < 0 || y2 < 0 || x2 >= n || y2 >= n || a[x2][y2] != 'G' && a[x2][y2] != 'M') continue;
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
126 ms |
6148 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
5 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
10 ms |
1508 KB |
Output is correct |
34 |
Correct |
11 ms |
1536 KB |
Output is correct |
35 |
Correct |
31 ms |
1604 KB |
Output is correct |
36 |
Correct |
11 ms |
1884 KB |
Output is correct |
37 |
Correct |
14 ms |
1792 KB |
Output is correct |
38 |
Correct |
39 ms |
1792 KB |
Output is correct |
39 |
Correct |
14 ms |
2248 KB |
Output is correct |
40 |
Correct |
16 ms |
2248 KB |
Output is correct |
41 |
Correct |
58 ms |
2232 KB |
Output is correct |
42 |
Correct |
18 ms |
2680 KB |
Output is correct |
43 |
Correct |
20 ms |
2684 KB |
Output is correct |
44 |
Correct |
65 ms |
2668 KB |
Output is correct |
45 |
Correct |
20 ms |
3184 KB |
Output is correct |
46 |
Correct |
20 ms |
3180 KB |
Output is correct |
47 |
Correct |
70 ms |
3148 KB |
Output is correct |
48 |
Correct |
25 ms |
3704 KB |
Output is correct |
49 |
Correct |
29 ms |
3672 KB |
Output is correct |
50 |
Correct |
85 ms |
3644 KB |
Output is correct |
51 |
Correct |
28 ms |
4188 KB |
Output is correct |
52 |
Correct |
27 ms |
4208 KB |
Output is correct |
53 |
Correct |
120 ms |
4204 KB |
Output is correct |
54 |
Correct |
31 ms |
4880 KB |
Output is correct |
55 |
Correct |
33 ms |
4824 KB |
Output is correct |
56 |
Correct |
130 ms |
4832 KB |
Output is correct |
57 |
Correct |
34 ms |
5476 KB |
Output is correct |
58 |
Correct |
40 ms |
5504 KB |
Output is correct |
59 |
Correct |
152 ms |
5448 KB |
Output is correct |
60 |
Correct |
37 ms |
6160 KB |
Output is correct |
61 |
Correct |
42 ms |
6160 KB |
Output is correct |
62 |
Correct |
166 ms |
6164 KB |
Output is correct |
63 |
Correct |
139 ms |
6168 KB |
Output is correct |
64 |
Correct |
272 ms |
6144 KB |
Output is correct |
65 |
Correct |
194 ms |
6160 KB |
Output is correct |
66 |
Correct |
184 ms |
6240 KB |
Output is correct |
67 |
Correct |
157 ms |
6160 KB |
Output is correct |
68 |
Correct |
68 ms |
6180 KB |
Output is correct |
69 |
Correct |
65 ms |
6208 KB |
Output is correct |
70 |
Correct |
49 ms |
6160 KB |
Output is correct |
71 |
Correct |
57 ms |
6200 KB |
Output is correct |
72 |
Correct |
39 ms |
6144 KB |
Output is correct |
73 |
Correct |
41 ms |
6136 KB |
Output is correct |
74 |
Correct |
83 ms |
6144 KB |
Output is correct |
75 |
Correct |
102 ms |
6160 KB |
Output is correct |
76 |
Correct |
94 ms |
6184 KB |
Output is correct |
77 |
Correct |
95 ms |
6204 KB |
Output is correct |
78 |
Correct |
106 ms |
6164 KB |
Output is correct |
79 |
Correct |
68 ms |
6200 KB |
Output is correct |
80 |
Correct |
87 ms |
6144 KB |
Output is correct |
81 |
Correct |
90 ms |
6212 KB |
Output is correct |
82 |
Correct |
83 ms |
6260 KB |
Output is correct |
83 |
Correct |
111 ms |
6120 KB |
Output is correct |
84 |
Correct |
129 ms |
6276 KB |
Output is correct |
85 |
Correct |
134 ms |
6128 KB |
Output is correct |
86 |
Correct |
115 ms |
6120 KB |
Output is correct |
87 |
Correct |
153 ms |
6148 KB |
Output is correct |
88 |
Correct |
110 ms |
6176 KB |
Output is correct |
89 |
Correct |
136 ms |
6180 KB |
Output is correct |
90 |
Correct |
110 ms |
6156 KB |
Output is correct |
91 |
Correct |
103 ms |
6180 KB |
Output is correct |
92 |
Correct |
117 ms |
6336 KB |
Output is correct |