| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338596 |
2020-12-23T13:17:42 Z |
blue |
Mecho (IOI09_mecho) |
C++11 |
|
983 ms |
8488 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
/*
Mecho takes at most S steps per minute.
Bees spread every minute.
(*) Restatement:
Mecho takes at most 1 step every minute.
Bees spread at the end of every S'th minute.
For every location, compute the number of minutes before the location cannot be occupied anymore.
For trees and hives this number is zero.
Consider hives as -1
Consider
*/
int N, S;
int grid[800*800]; //the number of minutes before this location cannot be occupied anymore.
int mecho;
int home;
vector<int> edge;
vector<int> dist(800*800, 1e9);
//LOOKS GOOD
int INF = 1e9;
int binary_search(int a, int b)
{
// cout << "____________________________\n binary search " << a << ' ' << b << '\n';
int m = (a+b)/2+1;
if(a == b) m = a;
//cout << mecho << ' ' << dist[mecho] << ' ' << home << '\n';
for(int i = 0; i < N*N; i++) dist[i] = INF;
queue<int> tbv;
dist[mecho] = m;
tbv.push(mecho);
int u;
while(!tbv.empty())
{
u = tbv.front();
// cout << u << ' ' << dist[u] << '\n';
tbv.pop();
vector<int> edge; //check down
edge.clear();
if(u % N != 0) edge.push_back(u-1);
if(u % N != N-1) edge.push_back(u+1);
if(u >= N) edge.push_back(u-N);
if(u < N*(N-1)) edge.push_back(u+N);
for(int v: edge)
{
if(dist[v] != INF) continue;
if(dist[u] + 1 >= grid[v]) continue;
dist[v] = dist[u] + 1;
tbv.push(v);
}
}
if(a == b)
{
if(dist[home] == INF) return -1;
else return a/S;
}
else
{
if(dist[home] == INF) return binary_search(a, m-1);
else return binary_search(m, b);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
char c;
cin >> N >> S;
for(int i = 0; i < N*N; i++)
{
cin >> c;
if(c == 'T') grid[i] = 0;
else if(c == 'G') grid[i] = INF;
else if(c == 'M')
{
grid[i] = INF;
mecho = i;
}
else if(c == 'D')
{
grid[i] = 0;
home = i;
}
else grid[i] = -1;
}
vector<int> visit(N*N, 0);
queue<int> tbv;
for(int i = 0; i < N*N; i++)
{
if(grid[i] != -1) continue;
grid[i] = 0;
tbv.push(i);
visit[i] = 1;
}
while(tbv.size() > 0)
{
int u = tbv.front();
tbv.pop();
edge.clear();
if(u % N > 0) edge.push_back(u-1);
if(u % N < N-1) edge.push_back(u+1);
if(u >= N) edge.push_back(u-N);
if(u < N*(N-1)) edge.push_back(u+N);
for(int v: edge)
{
if(visit[v]) continue;
if(grid[v] > grid[u] + S)
{
grid[v] = grid[u] + S;
tbv.push(v);
}
}
}
grid[home] = INF;
// for(int i = 0; i < N*N; i++)
// {
// cout << grid[i] << ' ';
// if(i % N == N-1) cout << '\n';
// }
cout << binary_search(0, 2e9) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 7 |
Correct |
470 ms |
8488 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
2924 KB |
Output isn't correct |
| 13 |
Incorrect |
3 ms |
2924 KB |
Output isn't correct |
| 14 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 17 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 23 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 28 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 30 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 31 |
Correct |
2 ms |
2924 KB |
Output is correct |
| 32 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 33 |
Correct |
13 ms |
3872 KB |
Output is correct |
| 34 |
Correct |
13 ms |
3820 KB |
Output is correct |
| 35 |
Correct |
160 ms |
3948 KB |
Output is correct |
| 36 |
Correct |
13 ms |
4076 KB |
Output is correct |
| 37 |
Correct |
13 ms |
4076 KB |
Output is correct |
| 38 |
Correct |
222 ms |
4076 KB |
Output is correct |
| 39 |
Correct |
18 ms |
4460 KB |
Output is correct |
| 40 |
Correct |
21 ms |
4460 KB |
Output is correct |
| 41 |
Correct |
273 ms |
4460 KB |
Output is correct |
| 42 |
Correct |
18 ms |
4844 KB |
Output is correct |
| 43 |
Correct |
31 ms |
4844 KB |
Output is correct |
| 44 |
Correct |
355 ms |
5100 KB |
Output is correct |
| 45 |
Correct |
24 ms |
5356 KB |
Output is correct |
| 46 |
Correct |
27 ms |
5228 KB |
Output is correct |
| 47 |
Correct |
439 ms |
5228 KB |
Output is correct |
| 48 |
Correct |
30 ms |
5740 KB |
Output is correct |
| 49 |
Correct |
37 ms |
5740 KB |
Output is correct |
| 50 |
Correct |
525 ms |
5996 KB |
Output is correct |
| 51 |
Correct |
36 ms |
6124 KB |
Output is correct |
| 52 |
Correct |
33 ms |
6124 KB |
Output is correct |
| 53 |
Correct |
618 ms |
6124 KB |
Output is correct |
| 54 |
Correct |
44 ms |
6764 KB |
Output is correct |
| 55 |
Correct |
44 ms |
6764 KB |
Output is correct |
| 56 |
Correct |
721 ms |
6884 KB |
Output is correct |
| 57 |
Correct |
39 ms |
7276 KB |
Output is correct |
| 58 |
Correct |
56 ms |
7404 KB |
Output is correct |
| 59 |
Correct |
815 ms |
7576 KB |
Output is correct |
| 60 |
Correct |
46 ms |
7916 KB |
Output is correct |
| 61 |
Correct |
44 ms |
8044 KB |
Output is correct |
| 62 |
Correct |
983 ms |
7916 KB |
Output is correct |
| 63 |
Correct |
300 ms |
7916 KB |
Output is correct |
| 64 |
Correct |
786 ms |
8172 KB |
Output is correct |
| 65 |
Correct |
525 ms |
8172 KB |
Output is correct |
| 66 |
Correct |
367 ms |
8044 KB |
Output is correct |
| 67 |
Correct |
346 ms |
8044 KB |
Output is correct |
| 68 |
Correct |
175 ms |
7916 KB |
Output is correct |
| 69 |
Correct |
130 ms |
7916 KB |
Output is correct |
| 70 |
Correct |
93 ms |
7916 KB |
Output is correct |
| 71 |
Correct |
102 ms |
7916 KB |
Output is correct |
| 72 |
Incorrect |
68 ms |
7916 KB |
Output isn't correct |
| 73 |
Incorrect |
166 ms |
8176 KB |
Output isn't correct |
| 74 |
Correct |
340 ms |
8172 KB |
Output is correct |
| 75 |
Correct |
295 ms |
8172 KB |
Output is correct |
| 76 |
Correct |
296 ms |
8172 KB |
Output is correct |
| 77 |
Correct |
298 ms |
8044 KB |
Output is correct |
| 78 |
Correct |
388 ms |
8044 KB |
Output is correct |
| 79 |
Correct |
360 ms |
8044 KB |
Output is correct |
| 80 |
Correct |
273 ms |
8044 KB |
Output is correct |
| 81 |
Correct |
314 ms |
8172 KB |
Output is correct |
| 82 |
Correct |
294 ms |
8044 KB |
Output is correct |
| 83 |
Correct |
388 ms |
8024 KB |
Output is correct |
| 84 |
Correct |
469 ms |
7916 KB |
Output is correct |
| 85 |
Correct |
382 ms |
8024 KB |
Output is correct |
| 86 |
Correct |
388 ms |
8172 KB |
Output is correct |
| 87 |
Correct |
380 ms |
8044 KB |
Output is correct |
| 88 |
Correct |
422 ms |
7916 KB |
Output is correct |
| 89 |
Correct |
549 ms |
7916 KB |
Output is correct |
| 90 |
Correct |
467 ms |
8044 KB |
Output is correct |
| 91 |
Correct |
489 ms |
7916 KB |
Output is correct |
| 92 |
Correct |
442 ms |
8172 KB |
Output is correct |
