| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338607 |
2020-12-23T13:25:20 Z |
blue |
Mecho (IOI09_mecho) |
C++11 |
|
1000 ms |
48796 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, v;
while(!tbv.empty())
{
u = tbv.front();
// cout << u << ' ' << dist[u] << '\n';
tbv.pop();
vector<int> edge; //check down
edge.clear();
if(u % N != 0)
{
v = u-1;
if(dist[v] == INF && dist[u] + 1 < grid[v])
{
dist[v] = dist[u] + 1;
tbv.push(v);
}
}
if(u % N != N-1)
{
v = u+1;
if(dist[v] == INF && dist[u] + 1 < grid[v])
{
dist[v] = dist[u] + 1;
tbv.push(v);
}
}
if(u >= N)
{
v = u-N;
if(dist[v] == INF && dist[u] + 1 < grid[v])
{
dist[v] = dist[u] + 1;
tbv.push(v);
}
}
if(u < N*(N+1))
{
v = u+N;
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;
// 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 |
492 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 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 |
114 ms |
8092 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 |
Execution timed out |
1081 ms |
48796 KB |
Time limit exceeded |
| 13 |
Incorrect |
1 ms |
364 KB |
Output isn't 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 |
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 |
364 KB |
Output is correct |
| 30 |
Correct |
1 ms |
364 KB |
Output is correct |
| 31 |
Correct |
1 ms |
492 KB |
Output is correct |
| 32 |
Correct |
1 ms |
492 KB |
Output is correct |
| 33 |
Correct |
7 ms |
1772 KB |
Output is correct |
| 34 |
Correct |
8 ms |
1772 KB |
Output is correct |
| 35 |
Correct |
22 ms |
1772 KB |
Output is correct |
| 36 |
Correct |
10 ms |
2284 KB |
Output is correct |
| 37 |
Correct |
9 ms |
2284 KB |
Output is correct |
| 38 |
Correct |
30 ms |
2284 KB |
Output is correct |
| 39 |
Correct |
12 ms |
2796 KB |
Output is correct |
| 40 |
Correct |
12 ms |
2796 KB |
Output is correct |
| 41 |
Correct |
37 ms |
2796 KB |
Output is correct |
| 42 |
Correct |
14 ms |
3308 KB |
Output is correct |
| 43 |
Correct |
16 ms |
3308 KB |
Output is correct |
| 44 |
Correct |
50 ms |
3252 KB |
Output is correct |
| 45 |
Correct |
18 ms |
3948 KB |
Output is correct |
| 46 |
Correct |
20 ms |
3948 KB |
Output is correct |
| 47 |
Correct |
71 ms |
3948 KB |
Output is correct |
| 48 |
Correct |
24 ms |
4716 KB |
Output is correct |
| 49 |
Correct |
21 ms |
4588 KB |
Output is correct |
| 50 |
Correct |
76 ms |
4716 KB |
Output is correct |
| 51 |
Correct |
29 ms |
5356 KB |
Output is correct |
| 52 |
Correct |
24 ms |
5356 KB |
Output is correct |
| 53 |
Correct |
103 ms |
5356 KB |
Output is correct |
| 54 |
Correct |
31 ms |
6124 KB |
Output is correct |
| 55 |
Correct |
28 ms |
6124 KB |
Output is correct |
| 56 |
Correct |
145 ms |
6124 KB |
Output is correct |
| 57 |
Correct |
32 ms |
7020 KB |
Output is correct |
| 58 |
Correct |
32 ms |
7020 KB |
Output is correct |
| 59 |
Correct |
148 ms |
7020 KB |
Output is correct |
| 60 |
Correct |
35 ms |
7916 KB |
Output is correct |
| 61 |
Correct |
35 ms |
7916 KB |
Output is correct |
| 62 |
Correct |
170 ms |
7916 KB |
Output is correct |
| 63 |
Correct |
114 ms |
7916 KB |
Output is correct |
| 64 |
Correct |
240 ms |
7916 KB |
Output is correct |
| 65 |
Correct |
170 ms |
7916 KB |
Output is correct |
| 66 |
Correct |
130 ms |
7916 KB |
Output is correct |
| 67 |
Correct |
121 ms |
7916 KB |
Output is correct |
| 68 |
Correct |
80 ms |
7916 KB |
Output is correct |
| 69 |
Correct |
69 ms |
7916 KB |
Output is correct |
| 70 |
Correct |
60 ms |
7916 KB |
Output is correct |
| 71 |
Correct |
60 ms |
7916 KB |
Output is correct |
| 72 |
Incorrect |
53 ms |
7916 KB |
Output isn't correct |
| 73 |
Incorrect |
64 ms |
8044 KB |
Output isn't correct |
| 74 |
Correct |
80 ms |
8044 KB |
Output is correct |
| 75 |
Correct |
80 ms |
8044 KB |
Output is correct |
| 76 |
Correct |
73 ms |
8044 KB |
Output is correct |
| 77 |
Correct |
80 ms |
8044 KB |
Output is correct |
| 78 |
Correct |
79 ms |
7916 KB |
Output is correct |
| 79 |
Correct |
73 ms |
7916 KB |
Output is correct |
| 80 |
Correct |
70 ms |
7916 KB |
Output is correct |
| 81 |
Correct |
73 ms |
7916 KB |
Output is correct |
| 82 |
Correct |
70 ms |
7916 KB |
Output is correct |
| 83 |
Correct |
86 ms |
7916 KB |
Output is correct |
| 84 |
Correct |
90 ms |
7916 KB |
Output is correct |
| 85 |
Correct |
85 ms |
7916 KB |
Output is correct |
| 86 |
Correct |
83 ms |
7916 KB |
Output is correct |
| 87 |
Correct |
83 ms |
7916 KB |
Output is correct |
| 88 |
Correct |
100 ms |
7916 KB |
Output is correct |
| 89 |
Correct |
103 ms |
7916 KB |
Output is correct |
| 90 |
Correct |
96 ms |
7916 KB |
Output is correct |
| 91 |
Correct |
100 ms |
7916 KB |
Output is correct |
| 92 |
Correct |
103 ms |
7916 KB |
Output is correct |
