Submission #142600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142600	2019-08-10T01:50:18 Z	WannnabeIOI	Mecho (IOI09_mecho)	C++14	46 / 100	22 ms	1400 KB

mecho

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 200; 
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

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	632 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Runtime error	19 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	2 ms	504 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	3 ms	504 KB	Output is correct
15	Correct	2 ms	508 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	508 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	508 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	552 KB	Output is correct
22	Correct	2 ms	508 KB	Output is correct
23	Correct	3 ms	504 KB	Output is correct
24	Correct	3 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	3 ms	504 KB	Output is correct
28	Correct	3 ms	504 KB	Output is correct
29	Correct	3 ms	504 KB	Output is correct
30	Correct	3 ms	504 KB	Output is correct
31	Correct	3 ms	504 KB	Output is correct
32	Correct	3 ms	504 KB	Output is correct
33	Runtime error	10 ms	888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	10 ms	1020 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	11 ms	1052 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	11 ms	1016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	11 ms	1016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	11 ms	1016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	12 ms	1016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	12 ms	1196 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	12 ms	1016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	13 ms	1016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	13 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	13 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	14 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	14 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	16 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	15 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	15 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	15 ms	1276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	16 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	16 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	16 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	18 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	17 ms	1264 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	17 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	19 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	22 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	21 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	20 ms	1176 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	20 ms	1400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	20 ms	1388 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	20 ms	1316 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	19 ms	1152 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	20 ms	1208 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	20 ms	1192 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	21 ms	1148 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	19 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	19 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	19 ms	1148 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	19 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	20 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	20 ms	1144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)