| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 286399 |
2020-08-30T11:10:47 Z |
abyyskit |
Mecho (IOI09_mecho) |
C++14 |
|
377 ms |
14836 KB |
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
#define x first
#define y second
int n;
int S;
struct spair{
int x;
int y;
};
bool inside(int a, int b){
if ((a >= 0 && b >= 0) && (a < n && b < n)){
return true;
}
return false;
}
struct node{
char c;
int d = -1;
bool vis = false;
spair sp = {-1, 0};
};
vector<vector<node>> g;
vector<pair<int, int>> D;
void bfs(vector<pair<int, int>> start){
queue<pair<pair<int, int>, int>> q;
FOR(i, 0, start.size()){
q.push({start[i], 0});
}
while (!q.empty()){
pair<pair<int, int>, int> tmp = q.front();
q.pop();
if (!g[tmp.x.x][tmp.x.y].vis){
g[tmp.x.x][tmp.x.y].vis = true;
g[tmp.x.x][tmp.x.y].d = tmp.y;
FOR(i, 0, 4){
int nx = tmp.x.x + D[i].x;
int ny = tmp.x.y + D[i].y;
if ((inside(nx, ny) &&!g[nx][ny].vis) &&
(g[nx][ny].c != 'T' && g[nx][ny].c != 'D')){
q.push({{nx, ny}, tmp.y + 1});
}
}
}
}
}
bool operator < (spair a, spair b){
if (a.x == b.x){
return a.y > b.y;
}
return a.x < b.x;
}
void fin_bfs(pair<int, int> end){
priority_queue<pair<spair, pair<int, int>>> q;
q.push({{INT_MAX - 1, 0}, end});
while(!q.empty()){
auto tmp = q.top();
q.pop();
// cout << tmp.x.x << " " << tmp.x.y << "\n";
if (g[tmp.y.x][tmp.y.y].sp < tmp.x){
// cout << "curent node: " << tmp.y.x << " " << tmp.y.y << "\n";
g[tmp.y.x][tmp.y.y].sp = tmp.x;
FOR(i, 0, 4){
int nx = tmp.y.x + D[i].x;
int ny = tmp.y.y + D[i].y;
if (inside(nx, ny)&& g[nx][ny].c != 'T'){
spair cur;
cur.x = tmp.x.x;
cur.y = tmp.x.y;
cur.y++;
if (cur.y > S){
cur.y = 1;
cur.x--;
}
if (cur.x > g[nx][ny].d){
cur.x = g[nx][ny].d;
cur.y = 1;
}
if (g[nx][ny].sp < cur){
q.push({cur, {nx, ny}});
}
}
}
}
}
}
int main(){
D = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
cin >> n >> S;
g.resize(n, vector<node>(n));
vector<pair<int, int>> start;
pair<int, int> end;
pair<int, int> s;
FOR(i, 0, n){
FOR(j, 0, n){
cin >> g[i][j].c;
if(g[i][j].c == 'H'){
start.pb({i, j});
}
if (g[i][j].c == 'D'){
end.x = i;
end.y = j;
}
if (g[i][j].c == 'M'){
s = {i, j};
}
}
}
bfs(start);
/* FOR(i, 0, g.size()){
FOR(j, 0, g[i].size()){
cout << g[i][j].d << " ";
}
cout << "\n";
}*/
fin_bfs(end);
/*FOR(i, 0, g.size()){
FOR(j, 0, g[i].size()){
cout << "(" << g[i][j].sp.x << ", " << g[i][j].sp.y << ") ";
}
cout << "\n";
}*/
if (g[s.x][s.y].sp.x == -1){
cout << "-1\n";
}
else{
cout << g[s.x][s.y].sp.x - 1 << "\n";
}
}
Compilation message
mecho.cpp: In function 'void bfs(std::vector<std::pair<int, int> >)':
mecho.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
32 | FOR(i, 0, start.size()){
| ~~~~~~~~~~~~~~~~~~
mecho.cpp:32:2: note: in expansion of macro 'FOR'
32 | FOR(i, 0, start.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
355 ms |
14204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
256 KB |
Output is correct |
| 11 |
Correct |
1 ms |
256 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
0 ms |
256 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
384 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
2 ms |
384 KB |
Output is correct |
| 30 |
Correct |
2 ms |
384 KB |
Output is correct |
| 31 |
Correct |
2 ms |
384 KB |
Output is correct |
| 32 |
Correct |
1 ms |
384 KB |
Output is correct |
| 33 |
Correct |
19 ms |
2816 KB |
Output is correct |
| 34 |
Correct |
17 ms |
2816 KB |
Output is correct |
| 35 |
Correct |
39 ms |
2816 KB |
Output is correct |
| 36 |
Correct |
21 ms |
3584 KB |
Output is correct |
| 37 |
Correct |
22 ms |
3584 KB |
Output is correct |
| 38 |
Correct |
44 ms |
3676 KB |
Output is correct |
| 39 |
Correct |
27 ms |
4480 KB |
Output is correct |
| 40 |
Correct |
27 ms |
4480 KB |
Output is correct |
| 41 |
Correct |
56 ms |
4480 KB |
Output is correct |
| 42 |
Correct |
33 ms |
5508 KB |
Output is correct |
| 43 |
Correct |
35 ms |
5624 KB |
Output is correct |
| 44 |
Correct |
70 ms |
5504 KB |
Output is correct |
| 45 |
Correct |
39 ms |
6528 KB |
Output is correct |
| 46 |
Correct |
41 ms |
6528 KB |
Output is correct |
| 47 |
Correct |
85 ms |
6608 KB |
Output is correct |
| 48 |
Correct |
50 ms |
7916 KB |
Output is correct |
| 49 |
Correct |
49 ms |
7808 KB |
Output is correct |
| 50 |
Correct |
106 ms |
7800 KB |
Output is correct |
| 51 |
Correct |
56 ms |
8960 KB |
Output is correct |
| 52 |
Correct |
56 ms |
8960 KB |
Output is correct |
| 53 |
Correct |
121 ms |
9120 KB |
Output is correct |
| 54 |
Correct |
64 ms |
10468 KB |
Output is correct |
| 55 |
Correct |
64 ms |
10368 KB |
Output is correct |
| 56 |
Correct |
139 ms |
10488 KB |
Output is correct |
| 57 |
Correct |
73 ms |
11904 KB |
Output is correct |
| 58 |
Correct |
74 ms |
11896 KB |
Output is correct |
| 59 |
Correct |
164 ms |
11896 KB |
Output is correct |
| 60 |
Correct |
82 ms |
13432 KB |
Output is correct |
| 61 |
Correct |
86 ms |
13560 KB |
Output is correct |
| 62 |
Correct |
183 ms |
13560 KB |
Output is correct |
| 63 |
Correct |
143 ms |
13560 KB |
Output is correct |
| 64 |
Correct |
142 ms |
13560 KB |
Output is correct |
| 65 |
Correct |
145 ms |
13560 KB |
Output is correct |
| 66 |
Correct |
146 ms |
13688 KB |
Output is correct |
| 67 |
Correct |
142 ms |
13560 KB |
Output is correct |
| 68 |
Correct |
120 ms |
13560 KB |
Output is correct |
| 69 |
Correct |
152 ms |
13560 KB |
Output is correct |
| 70 |
Correct |
115 ms |
13560 KB |
Output is correct |
| 71 |
Correct |
123 ms |
13688 KB |
Output is correct |
| 72 |
Correct |
149 ms |
13560 KB |
Output is correct |
| 73 |
Correct |
242 ms |
14328 KB |
Output is correct |
| 74 |
Correct |
372 ms |
14836 KB |
Output is correct |
| 75 |
Correct |
254 ms |
14380 KB |
Output is correct |
| 76 |
Correct |
245 ms |
14328 KB |
Output is correct |
| 77 |
Correct |
265 ms |
14500 KB |
Output is correct |
| 78 |
Correct |
253 ms |
14328 KB |
Output is correct |
| 79 |
Correct |
377 ms |
14776 KB |
Output is correct |
| 80 |
Correct |
261 ms |
14200 KB |
Output is correct |
| 81 |
Correct |
247 ms |
14288 KB |
Output is correct |
| 82 |
Correct |
312 ms |
14224 KB |
Output is correct |
| 83 |
Correct |
258 ms |
14072 KB |
Output is correct |
| 84 |
Correct |
368 ms |
14740 KB |
Output is correct |
| 85 |
Correct |
312 ms |
14112 KB |
Output is correct |
| 86 |
Correct |
284 ms |
14072 KB |
Output is correct |
| 87 |
Correct |
360 ms |
14108 KB |
Output is correct |
| 88 |
Correct |
338 ms |
14200 KB |
Output is correct |
| 89 |
Correct |
351 ms |
14748 KB |
Output is correct |
| 90 |
Correct |
356 ms |
14376 KB |
Output is correct |
| 91 |
Correct |
355 ms |
14744 KB |
Output is correct |
| 92 |
Correct |
350 ms |
14204 KB |
Output is correct |
