/**
* A binary search solution for IOI 2009 problem "mecho"
*
* This solution should score 100%
*
* Carl Hultquist, [email protected]
*/
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <utility>
#include <deque>
using namespace std;
#define MAX_N 2000
int cx[4] = {1, -1, 0, 0};
int cy[4] = {0, 0, 1, -1};
char mainMap[MAX_N][MAX_N];
bool reachable[MAX_N][MAX_N];
// The time that it takes the bees to reach any cell in the map
int beeDistance[MAX_N][MAX_N];
int n, s;
int dx, dy;
int mx, my;
/**
* Tests if Mecho is able to reach his home after staying with
* the honey for the given delay time.
*/
bool test(int delay)
{
// Check if the bees catch Mecho whilst he is still with
// the honey.
if (delay * s >= beeDistance[mx][my])
return false;
// Initialise data structures -- at the beginning of the search,
// Mecho has only reached the cell with the honey. Note that it
// is possible for the bees to catch Mecho at the honey -- but
// we checked for this case above, and so if we reach this point
// we know that Mecho is safe with the honey after the given
// delay.
memset(reachable, 0, sizeof(reachable));
deque<pair<int, pair<int, int> > > q;
q.push_back(make_pair(delay * s, make_pair(mx, my)));
reachable[mx][my] = true;
// Now do the main loop to see what other cells Mecho can reach.
while (!q.empty())
{
int distance = q.front().first;
int x = q.front().second.first;
int y = q.front().second.second;
q.pop_front();
// If Mecho has reached his home, then we are done.
if (mainMap[x][y] == 'D')
return true;
// Check neighbouring cells
for (int c = 0; c < 4; c++)
{
int nx = x + cx[c];
int ny = y + cy[c];
// Check that the cell is valid, that it is not a tree, and
// that Mecho can get here before the bees.
if (nx < 0 || nx >= n || ny < 0 || ny >= n || mainMap[nx][ny] == 'T' || (distance + 1) >= beeDistance[nx][ny] || reachable[nx][ny])
continue;
// All OK, so add it to the queue
q.push_back(make_pair(distance + 1, make_pair(nx, ny)));
reachable[nx][ny] = true;
}
}
// If we reach here, then Mecho was unable to reach his home.
return false;
}
int main(int argc, char **argv)
{
// Read in the data
cin >> n >> s;
deque<pair<int, int> > bq;
memset(beeDistance, -1, sizeof(beeDistance));
for (int i = 0; i < n; i++)
{
cin >> ws;
for (int j = 0; j < n; j++)
{
cin >> mainMap[i][j];
if (mainMap[i][j] == 'H')
{
bq.push_back(make_pair(i, j));
beeDistance[i][j] = 0;
}
else if (mainMap[i][j] == 'M')
{
mx = i;
my = j;
// Bees can travel through the location of the honey
mainMap[i][j] = 'G';
}
else if (mainMap[i][j] == 'D')
{
dx = i;
dy = j;
}
}
}
// Precompute the time that it takes the bees to reach any other
// cell in the map.
while (!bq.empty())
{
int x = bq.front().first;
int y = bq.front().second;
bq.pop_front();
for (int c = 0; c < 4; c++)
{
int nx = x + cx[c];
int ny = y + cy[c];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || mainMap[nx][ny] != 'G' || beeDistance[nx][ny] != -1)
continue;
beeDistance[nx][ny] = beeDistance[x][y] + s;
bq.push_back(make_pair(nx, ny));
}
}
// The bees can never enter Mecho's home, so set this to a large
// sentinel value.
beeDistance[dx][dy] = n * n * s;
// Binary search to find the maximum delay time.
int low = -1, high = 2 * n * n;
while (high - low > 1)
{
int mid = (low + high) >> 1;
if (test(mid))
low = mid;
else
high = mid;
}
cout << low << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19792 KB |
Output is correct |
2 |
Correct |
9 ms |
19792 KB |
Output is correct |
3 |
Correct |
9 ms |
19792 KB |
Output is correct |
4 |
Correct |
8 ms |
19792 KB |
Output is correct |
5 |
Correct |
9 ms |
19792 KB |
Output is correct |
6 |
Correct |
10 ms |
19836 KB |
Output is correct |
7 |
Correct |
126 ms |
22116 KB |
Output is correct |
8 |
Correct |
11 ms |
19792 KB |
Output is correct |
9 |
Correct |
8 ms |
19792 KB |
Output is correct |
10 |
Correct |
9 ms |
19792 KB |
Output is correct |
11 |
Correct |
11 ms |
19812 KB |
Output is correct |
12 |
Correct |
10 ms |
19920 KB |
Output is correct |
13 |
Correct |
9 ms |
19940 KB |
Output is correct |
14 |
Correct |
10 ms |
19920 KB |
Output is correct |
15 |
Correct |
11 ms |
19920 KB |
Output is correct |
16 |
Correct |
9 ms |
19920 KB |
Output is correct |
17 |
Correct |
9 ms |
19920 KB |
Output is correct |
18 |
Correct |
9 ms |
19920 KB |
Output is correct |
19 |
Correct |
9 ms |
19920 KB |
Output is correct |
20 |
Correct |
9 ms |
19920 KB |
Output is correct |
21 |
Correct |
9 ms |
19892 KB |
Output is correct |
22 |
Correct |
10 ms |
19960 KB |
Output is correct |
23 |
Correct |
9 ms |
19892 KB |
Output is correct |
24 |
Correct |
10 ms |
19880 KB |
Output is correct |
25 |
Correct |
9 ms |
19920 KB |
Output is correct |
26 |
Correct |
9 ms |
19920 KB |
Output is correct |
27 |
Correct |
9 ms |
19920 KB |
Output is correct |
28 |
Correct |
10 ms |
19920 KB |
Output is correct |
29 |
Correct |
9 ms |
19920 KB |
Output is correct |
30 |
Correct |
10 ms |
19920 KB |
Output is correct |
31 |
Correct |
10 ms |
20036 KB |
Output is correct |
32 |
Correct |
10 ms |
20032 KB |
Output is correct |
33 |
Correct |
20 ms |
20648 KB |
Output is correct |
34 |
Correct |
23 ms |
20600 KB |
Output is correct |
35 |
Correct |
38 ms |
20632 KB |
Output is correct |
36 |
Correct |
21 ms |
20816 KB |
Output is correct |
37 |
Correct |
24 ms |
20720 KB |
Output is correct |
38 |
Correct |
57 ms |
20772 KB |
Output is correct |
39 |
Correct |
25 ms |
20836 KB |
Output is correct |
40 |
Correct |
24 ms |
20896 KB |
Output is correct |
41 |
Correct |
55 ms |
20936 KB |
Output is correct |
42 |
Correct |
28 ms |
21072 KB |
Output is correct |
43 |
Correct |
30 ms |
21072 KB |
Output is correct |
44 |
Correct |
73 ms |
21136 KB |
Output is correct |
45 |
Correct |
32 ms |
21196 KB |
Output is correct |
46 |
Correct |
31 ms |
21124 KB |
Output is correct |
47 |
Correct |
75 ms |
21124 KB |
Output is correct |
48 |
Correct |
37 ms |
21288 KB |
Output is correct |
49 |
Correct |
35 ms |
21304 KB |
Output is correct |
50 |
Correct |
85 ms |
21304 KB |
Output is correct |
51 |
Correct |
41 ms |
21476 KB |
Output is correct |
52 |
Correct |
40 ms |
21448 KB |
Output is correct |
53 |
Correct |
107 ms |
21468 KB |
Output is correct |
54 |
Correct |
46 ms |
21704 KB |
Output is correct |
55 |
Correct |
45 ms |
21628 KB |
Output is correct |
56 |
Correct |
119 ms |
21600 KB |
Output is correct |
57 |
Correct |
54 ms |
21864 KB |
Output is correct |
58 |
Correct |
58 ms |
21876 KB |
Output is correct |
59 |
Correct |
203 ms |
21776 KB |
Output is correct |
60 |
Correct |
58 ms |
21960 KB |
Output is correct |
61 |
Correct |
55 ms |
22040 KB |
Output is correct |
62 |
Correct |
156 ms |
21960 KB |
Output is correct |
63 |
Correct |
152 ms |
22088 KB |
Output is correct |
64 |
Correct |
253 ms |
22060 KB |
Output is correct |
65 |
Correct |
196 ms |
22084 KB |
Output is correct |
66 |
Correct |
184 ms |
22024 KB |
Output is correct |
67 |
Correct |
169 ms |
21960 KB |
Output is correct |
68 |
Correct |
88 ms |
22080 KB |
Output is correct |
69 |
Correct |
104 ms |
22088 KB |
Output is correct |
70 |
Correct |
76 ms |
21960 KB |
Output is correct |
71 |
Correct |
84 ms |
22084 KB |
Output is correct |
72 |
Correct |
67 ms |
22104 KB |
Output is correct |
73 |
Correct |
68 ms |
22312 KB |
Output is correct |
74 |
Correct |
108 ms |
22208 KB |
Output is correct |
75 |
Correct |
116 ms |
22236 KB |
Output is correct |
76 |
Correct |
100 ms |
22320 KB |
Output is correct |
77 |
Correct |
98 ms |
22344 KB |
Output is correct |
78 |
Correct |
113 ms |
22304 KB |
Output is correct |
79 |
Correct |
98 ms |
22216 KB |
Output is correct |
80 |
Correct |
102 ms |
22212 KB |
Output is correct |
81 |
Correct |
102 ms |
22252 KB |
Output is correct |
82 |
Correct |
97 ms |
22344 KB |
Output is correct |
83 |
Correct |
121 ms |
22216 KB |
Output is correct |
84 |
Correct |
113 ms |
22332 KB |
Output is correct |
85 |
Correct |
121 ms |
22272 KB |
Output is correct |
86 |
Correct |
136 ms |
22304 KB |
Output is correct |
87 |
Correct |
125 ms |
22264 KB |
Output is correct |
88 |
Correct |
113 ms |
22180 KB |
Output is correct |
89 |
Correct |
115 ms |
22096 KB |
Output is correct |
90 |
Correct |
120 ms |
22216 KB |
Output is correct |
91 |
Correct |
128 ms |
22216 KB |
Output is correct |
92 |
Correct |
128 ms |
22216 KB |
Output is correct |