| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338602 |
2020-12-23T13:21:02 Z |
blue |
Mecho (IOI09_mecho) |
C++11 |
|
1000 ms |
8172 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;
int dist[800*800];
//LOOKS GOOD
int INF = 2e9;
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 |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
471 ms |
8044 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Execution timed out |
1080 ms |
5432 KB |
Time limit exceeded |
| 13 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 14 |
Correct |
2 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
512 KB |
Output is correct |
| 18 |
Correct |
1 ms |
504 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
364 KB |
Output is correct |
| 21 |
Correct |
1 ms |
364 KB |
Output is correct |
| 22 |
Correct |
1 ms |
364 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
1 ms |
364 KB |
Output is correct |
| 25 |
Correct |
1 ms |
364 KB |
Output is correct |
| 26 |
Correct |
1 ms |
364 KB |
Output is correct |
| 27 |
Correct |
1 ms |
364 KB |
Output is correct |
| 28 |
Correct |
1 ms |
364 KB |
Output is correct |
| 29 |
Correct |
1 ms |
492 KB |
Output is correct |
| 30 |
Correct |
1 ms |
492 KB |
Output is correct |
| 31 |
Correct |
1 ms |
512 KB |
Output is correct |
| 32 |
Correct |
1 ms |
492 KB |
Output is correct |
| 33 |
Correct |
10 ms |
1772 KB |
Output is correct |
| 34 |
Correct |
11 ms |
1772 KB |
Output is correct |
| 35 |
Correct |
160 ms |
1772 KB |
Output is correct |
| 36 |
Correct |
11 ms |
2284 KB |
Output is correct |
| 37 |
Correct |
10 ms |
2284 KB |
Output is correct |
| 38 |
Correct |
218 ms |
2284 KB |
Output is correct |
| 39 |
Correct |
15 ms |
2796 KB |
Output is correct |
| 40 |
Correct |
19 ms |
2796 KB |
Output is correct |
| 41 |
Correct |
334 ms |
2796 KB |
Output is correct |
| 42 |
Correct |
14 ms |
3308 KB |
Output is correct |
| 43 |
Correct |
29 ms |
3308 KB |
Output is correct |
| 44 |
Correct |
356 ms |
3308 KB |
Output is correct |
| 45 |
Correct |
26 ms |
3972 KB |
Output is correct |
| 46 |
Correct |
26 ms |
3948 KB |
Output is correct |
| 47 |
Correct |
435 ms |
3948 KB |
Output is correct |
| 48 |
Correct |
26 ms |
4588 KB |
Output is correct |
| 49 |
Correct |
38 ms |
4716 KB |
Output is correct |
| 50 |
Correct |
523 ms |
4644 KB |
Output is correct |
| 51 |
Correct |
31 ms |
5356 KB |
Output is correct |
| 52 |
Correct |
29 ms |
5356 KB |
Output is correct |
| 53 |
Correct |
620 ms |
5484 KB |
Output is correct |
| 54 |
Correct |
40 ms |
6124 KB |
Output is correct |
| 55 |
Correct |
40 ms |
6124 KB |
Output is correct |
| 56 |
Correct |
724 ms |
6420 KB |
Output is correct |
| 57 |
Correct |
35 ms |
7148 KB |
Output is correct |
| 58 |
Correct |
51 ms |
7020 KB |
Output is correct |
| 59 |
Correct |
946 ms |
7020 KB |
Output is correct |
| 60 |
Correct |
40 ms |
7916 KB |
Output is correct |
| 61 |
Correct |
45 ms |
7916 KB |
Output is correct |
| 62 |
Correct |
980 ms |
8044 KB |
Output is correct |
| 63 |
Correct |
296 ms |
7916 KB |
Output is correct |
| 64 |
Correct |
766 ms |
8172 KB |
Output is correct |
| 65 |
Correct |
516 ms |
8044 KB |
Output is correct |
| 66 |
Correct |
373 ms |
8044 KB |
Output is correct |
| 67 |
Correct |
330 ms |
8172 KB |
Output is correct |
| 68 |
Correct |
168 ms |
7916 KB |
Output is correct |
| 69 |
Correct |
123 ms |
7892 KB |
Output is correct |
| 70 |
Correct |
88 ms |
7916 KB |
Output is correct |
| 71 |
Correct |
93 ms |
8044 KB |
Output is correct |
| 72 |
Incorrect |
61 ms |
7916 KB |
Output isn't correct |
| 73 |
Incorrect |
152 ms |
8044 KB |
Output isn't correct |
| 74 |
Correct |
373 ms |
8172 KB |
Output is correct |
| 75 |
Correct |
284 ms |
8172 KB |
Output is correct |
| 76 |
Correct |
260 ms |
8172 KB |
Output is correct |
| 77 |
Correct |
300 ms |
8172 KB |
Output is correct |
| 78 |
Correct |
428 ms |
7916 KB |
Output is correct |
| 79 |
Correct |
321 ms |
8044 KB |
Output is correct |
| 80 |
Correct |
259 ms |
7916 KB |
Output is correct |
| 81 |
Correct |
301 ms |
7916 KB |
Output is correct |
| 82 |
Correct |
280 ms |
7916 KB |
Output is correct |
| 83 |
Correct |
373 ms |
8044 KB |
Output is correct |
| 84 |
Correct |
452 ms |
8044 KB |
Output is correct |
| 85 |
Correct |
369 ms |
8044 KB |
Output is correct |
| 86 |
Correct |
385 ms |
8044 KB |
Output is correct |
| 87 |
Correct |
379 ms |
7916 KB |
Output is correct |
| 88 |
Correct |
421 ms |
7916 KB |
Output is correct |
| 89 |
Correct |
551 ms |
7916 KB |
Output is correct |
| 90 |
Correct |
469 ms |
7916 KB |
Output is correct |
| 91 |
Correct |
477 ms |
8108 KB |
Output is correct |
| 92 |
Correct |
435 ms |
7916 KB |
Output is correct |
