답안 #445349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445349	2021-07-17T14:40:39 Z	233	Mecho (IOI09_mecho)	C++17	100 / 100	259 ms	22388 KB

mecho

/**
 * A binary search solution for IOI 2009 problem "mecho"
 *
 * This solution should score 100%
 *
 * Carl Hultquist, [email protected]
 */

#include <iostream>
#include <cstring>
#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;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	19788 KB	Output is correct
2	Correct	10 ms	19788 KB	Output is correct
3	Correct	10 ms	19892 KB	Output is correct
4	Correct	10 ms	19788 KB	Output is correct
5	Correct	10 ms	19868 KB	Output is correct
6	Correct	10 ms	19788 KB	Output is correct
7	Correct	142 ms	22140 KB	Output is correct
8	Correct	11 ms	19788 KB	Output is correct
9	Correct	10 ms	19788 KB	Output is correct
10	Correct	11 ms	19908 KB	Output is correct
11	Correct	10 ms	19788 KB	Output is correct
12	Correct	10 ms	19916 KB	Output is correct
13	Correct	10 ms	19888 KB	Output is correct
14	Correct	12 ms	19916 KB	Output is correct
15	Correct	11 ms	19892 KB	Output is correct
16	Correct	10 ms	19916 KB	Output is correct
17	Correct	10 ms	19916 KB	Output is correct
18	Correct	10 ms	19916 KB	Output is correct
19	Correct	11 ms	19932 KB	Output is correct
20	Correct	10 ms	19916 KB	Output is correct
21	Correct	11 ms	19916 KB	Output is correct
22	Correct	11 ms	19928 KB	Output is correct
23	Correct	11 ms	19916 KB	Output is correct
24	Correct	11 ms	19916 KB	Output is correct
25	Correct	12 ms	19916 KB	Output is correct
26	Correct	11 ms	19916 KB	Output is correct
27	Correct	11 ms	19916 KB	Output is correct
28	Correct	11 ms	20012 KB	Output is correct
29	Correct	11 ms	20020 KB	Output is correct
30	Correct	11 ms	19944 KB	Output is correct
31	Correct	12 ms	19996 KB	Output is correct
32	Correct	12 ms	19944 KB	Output is correct
33	Correct	20 ms	20672 KB	Output is correct
34	Correct	21 ms	20556 KB	Output is correct
35	Correct	40 ms	20656 KB	Output is correct
36	Correct	23 ms	20816 KB	Output is correct
37	Correct	23 ms	20676 KB	Output is correct
38	Correct	50 ms	20792 KB	Output is correct
39	Correct	28 ms	20928 KB	Output is correct
40	Correct	27 ms	20932 KB	Output is correct
41	Correct	63 ms	20912 KB	Output is correct
42	Correct	30 ms	21052 KB	Output is correct
43	Correct	31 ms	21060 KB	Output is correct
44	Correct	76 ms	20992 KB	Output is correct
45	Correct	34 ms	21168 KB	Output is correct
46	Correct	34 ms	21188 KB	Output is correct
47	Correct	88 ms	21132 KB	Output is correct
48	Correct	38 ms	21308 KB	Output is correct
49	Correct	38 ms	21316 KB	Output is correct
50	Correct	102 ms	21316 KB	Output is correct
51	Correct	43 ms	21500 KB	Output is correct
52	Correct	44 ms	21552 KB	Output is correct
53	Correct	124 ms	21444 KB	Output is correct
54	Correct	48 ms	21660 KB	Output is correct
55	Correct	48 ms	21676 KB	Output is correct
56	Correct	150 ms	21740 KB	Output is correct
57	Correct	54 ms	21824 KB	Output is correct
58	Correct	53 ms	21872 KB	Output is correct
59	Correct	166 ms	21888 KB	Output is correct
60	Correct	59 ms	21956 KB	Output is correct
61	Correct	59 ms	21964 KB	Output is correct
62	Correct	190 ms	22060 KB	Output is correct
63	Correct	152 ms	22060 KB	Output is correct
64	Correct	259 ms	22000 KB	Output is correct
65	Correct	210 ms	22084 KB	Output is correct
66	Correct	170 ms	22008 KB	Output is correct
67	Correct	165 ms	21988 KB	Output is correct
68	Correct	94 ms	21960 KB	Output is correct
69	Correct	94 ms	22020 KB	Output is correct
70	Correct	81 ms	22008 KB	Output is correct
71	Correct	90 ms	22020 KB	Output is correct
72	Correct	77 ms	22064 KB	Output is correct
73	Correct	79 ms	22212 KB	Output is correct
74	Correct	108 ms	22256 KB	Output is correct
75	Correct	130 ms	22388 KB	Output is correct
76	Correct	114 ms	22212 KB	Output is correct
77	Correct	112 ms	22268 KB	Output is correct
78	Correct	129 ms	22212 KB	Output is correct
79	Correct	96 ms	22232 KB	Output is correct
80	Correct	110 ms	22220 KB	Output is correct
81	Correct	119 ms	22228 KB	Output is correct
82	Correct	109 ms	22196 KB	Output is correct
83	Correct	130 ms	22208 KB	Output is correct
84	Correct	122 ms	22268 KB	Output is correct
85	Correct	128 ms	22224 KB	Output is correct
86	Correct	127 ms	22236 KB	Output is correct
87	Correct	125 ms	22236 KB	Output is correct
88	Correct	130 ms	22084 KB	Output is correct
89	Correct	135 ms	22256 KB	Output is correct
90	Correct	135 ms	22112 KB	Output is correct
91	Correct	133 ms	22212 KB	Output is correct
92	Correct	142 ms	22156 KB	Output is correct