| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338595 |
2020-12-23T13:16:51 Z |
blue |
Mecho (IOI09_mecho) |
C++11 |
|
1000 ms |
8684 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, 2e9) << '\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 |
3 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 |
531 ms |
8044 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
2924 KB |
Output isn't correct |
| 13 |
Incorrect |
3 ms |
2796 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 |
2 ms |
2796 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 22 |
Correct |
4 ms |
2796 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 24 |
Correct |
3 ms |
2924 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 |
2892 KB |
Output is correct |
| 32 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 33 |
Correct |
18 ms |
3820 KB |
Output is correct |
| 34 |
Correct |
18 ms |
3820 KB |
Output is correct |
| 35 |
Correct |
167 ms |
3820 KB |
Output is correct |
| 36 |
Correct |
25 ms |
4076 KB |
Output is correct |
| 37 |
Correct |
20 ms |
4204 KB |
Output is correct |
| 38 |
Correct |
236 ms |
4588 KB |
Output is correct |
| 39 |
Correct |
27 ms |
4376 KB |
Output is correct |
| 40 |
Correct |
30 ms |
4588 KB |
Output is correct |
| 41 |
Correct |
297 ms |
4716 KB |
Output is correct |
| 42 |
Correct |
29 ms |
5100 KB |
Output is correct |
| 43 |
Correct |
44 ms |
5104 KB |
Output is correct |
| 44 |
Correct |
407 ms |
5228 KB |
Output is correct |
| 45 |
Correct |
42 ms |
5276 KB |
Output is correct |
| 46 |
Correct |
41 ms |
5560 KB |
Output is correct |
| 47 |
Correct |
521 ms |
5272 KB |
Output is correct |
| 48 |
Correct |
46 ms |
5996 KB |
Output is correct |
| 49 |
Correct |
59 ms |
5868 KB |
Output is correct |
| 50 |
Correct |
571 ms |
5716 KB |
Output is correct |
| 51 |
Correct |
53 ms |
6508 KB |
Output is correct |
| 52 |
Correct |
54 ms |
6508 KB |
Output is correct |
| 53 |
Correct |
668 ms |
6212 KB |
Output is correct |
| 54 |
Correct |
68 ms |
7200 KB |
Output is correct |
| 55 |
Correct |
66 ms |
7204 KB |
Output is correct |
| 56 |
Correct |
794 ms |
7012 KB |
Output is correct |
| 57 |
Correct |
66 ms |
7800 KB |
Output is correct |
| 58 |
Correct |
84 ms |
7704 KB |
Output is correct |
| 59 |
Correct |
876 ms |
7912 KB |
Output is correct |
| 60 |
Correct |
77 ms |
8300 KB |
Output is correct |
| 61 |
Correct |
74 ms |
8416 KB |
Output is correct |
| 62 |
Execution timed out |
1068 ms |
8368 KB |
Time limit exceeded |
| 63 |
Correct |
336 ms |
8420 KB |
Output is correct |
| 64 |
Correct |
804 ms |
8424 KB |
Output is correct |
| 65 |
Correct |
560 ms |
8428 KB |
Output is correct |
| 66 |
Correct |
438 ms |
8300 KB |
Output is correct |
| 67 |
Correct |
416 ms |
8428 KB |
Output is correct |
| 68 |
Correct |
211 ms |
8300 KB |
Output is correct |
| 69 |
Correct |
160 ms |
8300 KB |
Output is correct |
| 70 |
Correct |
123 ms |
8428 KB |
Output is correct |
| 71 |
Correct |
130 ms |
8300 KB |
Output is correct |
| 72 |
Incorrect |
95 ms |
8300 KB |
Output isn't correct |
| 73 |
Incorrect |
187 ms |
8556 KB |
Output isn't correct |
| 74 |
Correct |
431 ms |
8612 KB |
Output is correct |
| 75 |
Correct |
331 ms |
8556 KB |
Output is correct |
| 76 |
Correct |
298 ms |
8676 KB |
Output is correct |
| 77 |
Correct |
357 ms |
8556 KB |
Output is correct |
| 78 |
Correct |
403 ms |
8556 KB |
Output is correct |
| 79 |
Correct |
362 ms |
8684 KB |
Output is correct |
| 80 |
Correct |
307 ms |
8428 KB |
Output is correct |
| 81 |
Correct |
341 ms |
8556 KB |
Output is correct |
| 82 |
Correct |
319 ms |
8532 KB |
Output is correct |
| 83 |
Correct |
420 ms |
8556 KB |
Output is correct |
| 84 |
Correct |
495 ms |
8536 KB |
Output is correct |
| 85 |
Correct |
370 ms |
8556 KB |
Output is correct |
| 86 |
Correct |
415 ms |
8684 KB |
Output is correct |
| 87 |
Correct |
403 ms |
8556 KB |
Output is correct |
| 88 |
Correct |
446 ms |
8556 KB |
Output is correct |
| 89 |
Correct |
641 ms |
8556 KB |
Output is correct |
| 90 |
Correct |
497 ms |
8684 KB |
Output is correct |
| 91 |
Correct |
567 ms |
8684 KB |
Output is correct |
| 92 |
Correct |
484 ms |
8556 KB |
Output is correct |
