| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338623 |
2020-12-23T14:03:59 Z |
blue |
Mecho (IOI09_mecho) |
C++11 |
|
333 ms |
8120 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];
int INF = 15e8;
int binary_search(int a, int b)
{
int m = (a+b)/2+1;
if(a == b) m = a;
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();
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(dist[v] == INF && dist[u] + 1 < grid[v])
{
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;
}
int visit[N*N];
for(int i = 0; i < N*N; i++) visit[i] = 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;
cout << binary_search(0, grid[mecho]-1) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 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 |
158 ms |
8048 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 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 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 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 |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 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 |
496 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 |
364 KB |
Output is correct |
| 30 |
Correct |
1 ms |
364 KB |
Output is correct |
| 31 |
Correct |
1 ms |
364 KB |
Output is correct |
| 32 |
Correct |
1 ms |
364 KB |
Output is correct |
| 33 |
Correct |
7 ms |
1772 KB |
Output is correct |
| 34 |
Correct |
8 ms |
1772 KB |
Output is correct |
| 35 |
Correct |
46 ms |
1900 KB |
Output is correct |
| 36 |
Correct |
9 ms |
2284 KB |
Output is correct |
| 37 |
Correct |
11 ms |
2284 KB |
Output is correct |
| 38 |
Correct |
63 ms |
2284 KB |
Output is correct |
| 39 |
Correct |
11 ms |
2796 KB |
Output is correct |
| 40 |
Correct |
14 ms |
2796 KB |
Output is correct |
| 41 |
Correct |
83 ms |
2796 KB |
Output is correct |
| 42 |
Correct |
14 ms |
3436 KB |
Output is correct |
| 43 |
Correct |
16 ms |
3308 KB |
Output is correct |
| 44 |
Correct |
100 ms |
3308 KB |
Output is correct |
| 45 |
Correct |
16 ms |
3948 KB |
Output is correct |
| 46 |
Correct |
20 ms |
3948 KB |
Output is correct |
| 47 |
Correct |
123 ms |
3948 KB |
Output is correct |
| 48 |
Correct |
20 ms |
4588 KB |
Output is correct |
| 49 |
Correct |
24 ms |
4588 KB |
Output is correct |
| 50 |
Correct |
153 ms |
4588 KB |
Output is correct |
| 51 |
Correct |
23 ms |
5356 KB |
Output is correct |
| 52 |
Correct |
28 ms |
5356 KB |
Output is correct |
| 53 |
Correct |
177 ms |
5356 KB |
Output is correct |
| 54 |
Correct |
27 ms |
6124 KB |
Output is correct |
| 55 |
Correct |
32 ms |
6124 KB |
Output is correct |
| 56 |
Correct |
212 ms |
6160 KB |
Output is correct |
| 57 |
Correct |
30 ms |
6892 KB |
Output is correct |
| 58 |
Correct |
37 ms |
7020 KB |
Output is correct |
| 59 |
Correct |
243 ms |
7020 KB |
Output is correct |
| 60 |
Correct |
36 ms |
7916 KB |
Output is correct |
| 61 |
Correct |
42 ms |
7916 KB |
Output is correct |
| 62 |
Correct |
286 ms |
8044 KB |
Output is correct |
| 63 |
Correct |
139 ms |
7788 KB |
Output is correct |
| 64 |
Correct |
333 ms |
7916 KB |
Output is correct |
| 65 |
Correct |
219 ms |
7916 KB |
Output is correct |
| 66 |
Correct |
179 ms |
7916 KB |
Output is correct |
| 67 |
Correct |
163 ms |
7916 KB |
Output is correct |
| 68 |
Correct |
98 ms |
7916 KB |
Output is correct |
| 69 |
Correct |
93 ms |
7916 KB |
Output is correct |
| 70 |
Correct |
58 ms |
7852 KB |
Output is correct |
| 71 |
Correct |
60 ms |
7916 KB |
Output is correct |
| 72 |
Correct |
51 ms |
7916 KB |
Output is correct |
| 73 |
Correct |
77 ms |
8044 KB |
Output is correct |
| 74 |
Correct |
128 ms |
8044 KB |
Output is correct |
| 75 |
Correct |
106 ms |
8044 KB |
Output is correct |
| 76 |
Correct |
97 ms |
8044 KB |
Output is correct |
| 77 |
Correct |
108 ms |
8044 KB |
Output is correct |
| 78 |
Correct |
130 ms |
7916 KB |
Output is correct |
| 79 |
Correct |
114 ms |
7916 KB |
Output is correct |
| 80 |
Correct |
101 ms |
7916 KB |
Output is correct |
| 81 |
Correct |
111 ms |
8044 KB |
Output is correct |
| 82 |
Correct |
99 ms |
7916 KB |
Output is correct |
| 83 |
Correct |
124 ms |
7916 KB |
Output is correct |
| 84 |
Correct |
149 ms |
7916 KB |
Output is correct |
| 85 |
Correct |
125 ms |
8044 KB |
Output is correct |
| 86 |
Correct |
131 ms |
8044 KB |
Output is correct |
| 87 |
Correct |
130 ms |
8120 KB |
Output is correct |
| 88 |
Correct |
147 ms |
8044 KB |
Output is correct |
| 89 |
Correct |
179 ms |
7916 KB |
Output is correct |
| 90 |
Correct |
154 ms |
7916 KB |
Output is correct |
| 91 |
Correct |
163 ms |
7916 KB |
Output is correct |
| 92 |
Correct |
147 ms |
7916 KB |
Output is correct |
