| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338590 |
2020-12-23T13:12:57 Z |
blue |
Mecho (IOI09_mecho) |
C++11 |
|
1000 ms |
8812 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()
{
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, INF) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 7 |
Correct |
540 ms |
8684 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 12 |
Incorrect |
3 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 |
2796 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 17 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 23 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 24 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 25 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 26 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 27 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 28 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 29 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 30 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 31 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 32 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 33 |
Correct |
18 ms |
3820 KB |
Output is correct |
| 34 |
Correct |
19 ms |
3820 KB |
Output is correct |
| 35 |
Correct |
209 ms |
3820 KB |
Output is correct |
| 36 |
Correct |
20 ms |
4076 KB |
Output is correct |
| 37 |
Correct |
20 ms |
4076 KB |
Output is correct |
| 38 |
Correct |
265 ms |
4076 KB |
Output is correct |
| 39 |
Correct |
26 ms |
4460 KB |
Output is correct |
| 40 |
Correct |
29 ms |
4460 KB |
Output is correct |
| 41 |
Correct |
285 ms |
4588 KB |
Output is correct |
| 42 |
Correct |
28 ms |
4844 KB |
Output is correct |
| 43 |
Correct |
44 ms |
4844 KB |
Output is correct |
| 44 |
Correct |
411 ms |
5100 KB |
Output is correct |
| 45 |
Correct |
36 ms |
5228 KB |
Output is correct |
| 46 |
Correct |
39 ms |
5228 KB |
Output is correct |
| 47 |
Correct |
446 ms |
5484 KB |
Output is correct |
| 48 |
Correct |
46 ms |
5612 KB |
Output is correct |
| 49 |
Correct |
66 ms |
5612 KB |
Output is correct |
| 50 |
Correct |
534 ms |
5740 KB |
Output is correct |
| 51 |
Correct |
51 ms |
6124 KB |
Output is correct |
| 52 |
Correct |
50 ms |
6124 KB |
Output is correct |
| 53 |
Correct |
619 ms |
6124 KB |
Output is correct |
| 54 |
Correct |
65 ms |
6764 KB |
Output is correct |
| 55 |
Correct |
75 ms |
6636 KB |
Output is correct |
| 56 |
Correct |
735 ms |
6892 KB |
Output is correct |
| 57 |
Correct |
62 ms |
7788 KB |
Output is correct |
| 58 |
Correct |
78 ms |
7788 KB |
Output is correct |
| 59 |
Correct |
835 ms |
7932 KB |
Output is correct |
| 60 |
Correct |
73 ms |
8428 KB |
Output is correct |
| 61 |
Correct |
70 ms |
8428 KB |
Output is correct |
| 62 |
Execution timed out |
1079 ms |
8684 KB |
Time limit exceeded |
| 63 |
Correct |
326 ms |
8428 KB |
Output is correct |
| 64 |
Correct |
789 ms |
8556 KB |
Output is correct |
| 65 |
Correct |
546 ms |
8564 KB |
Output is correct |
| 66 |
Correct |
395 ms |
8556 KB |
Output is correct |
| 67 |
Correct |
366 ms |
8428 KB |
Output is correct |
| 68 |
Correct |
197 ms |
8428 KB |
Output is correct |
| 69 |
Correct |
162 ms |
8428 KB |
Output is correct |
| 70 |
Correct |
127 ms |
8556 KB |
Output is correct |
| 71 |
Correct |
126 ms |
8428 KB |
Output is correct |
| 72 |
Incorrect |
93 ms |
8428 KB |
Output isn't correct |
| 73 |
Incorrect |
190 ms |
8556 KB |
Output isn't correct |
| 74 |
Correct |
368 ms |
8736 KB |
Output is correct |
| 75 |
Correct |
318 ms |
8684 KB |
Output is correct |
| 76 |
Correct |
316 ms |
8684 KB |
Output is correct |
| 77 |
Correct |
334 ms |
8660 KB |
Output is correct |
| 78 |
Correct |
413 ms |
8684 KB |
Output is correct |
| 79 |
Correct |
378 ms |
8556 KB |
Output is correct |
| 80 |
Correct |
298 ms |
8556 KB |
Output is correct |
| 81 |
Correct |
353 ms |
8556 KB |
Output is correct |
| 82 |
Correct |
330 ms |
8812 KB |
Output is correct |
| 83 |
Correct |
413 ms |
8668 KB |
Output is correct |
| 84 |
Correct |
470 ms |
8684 KB |
Output is correct |
| 85 |
Correct |
361 ms |
8556 KB |
Output is correct |
| 86 |
Correct |
410 ms |
8812 KB |
Output is correct |
| 87 |
Correct |
406 ms |
8556 KB |
Output is correct |
| 88 |
Correct |
457 ms |
8684 KB |
Output is correct |
| 89 |
Correct |
604 ms |
8556 KB |
Output is correct |
| 90 |
Correct |
496 ms |
8556 KB |
Output is correct |
| 91 |
Correct |
513 ms |
8684 KB |
Output is correct |
| 92 |
Correct |
459 ms |
8684 KB |
Output is correct |
