Submission #484157

# Submission time Handle Problem Language Result Execution time Memory
484157 2021-11-02T08:33:39 Z nehasane Mecho (IOI09_mecho) C++14
44 / 100
674 ms 10180 KB
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 800;
vector <string> field(MAX_N);
bool bees_visited[MAX_N][MAX_N], mecho_visited[MAX_N][MAX_N];
int mecho_dis[MAX_N][MAX_N], bees_dis[MAX_N][MAX_N], eating_dis[MAX_N][MAX_N];
queue <pair <int, int>> mecho_q, bees_q;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int n, s;
bool valid_sq(int x, int y, bool is_mecho){
    if (x >= 0 && x < n && y >= 0 && y < n){
        if (is_mecho && (field[x][y] == 'G' || field[x][y] == 'D' || field[x][y] == 'M'))
            return true;
        else if (!is_mecho && (field[x][y] == 'G' || field[x][y] == 'M'))
            return true;
        return false;
    }
    return false;
}
int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> field[i];
    vector <pair <int, int>> hives;
    int startx, starty, home_x, home_y;
    //find Mecho's position
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (field[i][j] == 'M'){
                startx = i;
                starty = j;
            }else if (field[i][j] == 'H'){
                hives.push_back({i, j});
            }else if (field[i][j] == 'D'){
                home_x = i;
                home_y = j;
            }
        }
    }
    int l = 0, r = n*n;
    while (l <= r){
        int eating_time = (l + r) / 2;
        memset(bees_visited, false, sizeof(bees_visited));
        memset(mecho_visited, false, sizeof(mecho_visited));
        memset(bees_dis, 0, sizeof(bees_dis));
        memset(mecho_dis, 0, sizeof(mecho_dis));
        //move bees
        for (auto i : hives){
            bees_q.push({i.first, i.second});
            bees_visited[i.first][i.second] = true;
        }
        while (!bees_q.empty()){
            int x = bees_q.front().first, y = bees_q.front().second;
            bees_q.pop();
            for (int i = 0; i < 4; i++){
                int nx = x + dx[i], ny = y + dy[i];
                if (valid_sq(nx, ny, false) && !bees_visited[nx][ny]){
                    if (eating_dis[x][y] < eating_time){
                        eating_dis[nx][ny] = eating_dis[x][y] + 1;
                    }else{
                        bees_dis[nx][ny] = bees_dis[x][y] + 1;
                        eating_dis[nx][ny] = INT_MAX;
                    }
                    bees_q.push({nx, ny});
                    bees_visited[nx][ny] = true;
                }
            }
        }
        mecho_q.push({startx, starty});
        mecho_visited[startx][starty] = true;
        if (bees_dis[startx][starty] <= eating_time)
            mecho_q.pop();
        while (!mecho_q.empty()){
            int x = mecho_q.front().first, y = mecho_q.front().second;
            mecho_q.pop();
            for (int i = 0; i < 4; i++){
                int nx = x + dx[i], ny = y + dy[i];
                if (valid_sq(nx, ny, true) && !mecho_visited[nx][ny] && (mecho_dis[x][y] + 1) / s < bees_dis[nx][ny]){
                    mecho_visited[nx][ny] = true;
                    mecho_q.push({nx, ny});
                    mecho_dis[nx][ny] = mecho_dis[x][y] + 1;
                }
            }
        }
        bool mecho_reached = false;
        for (int i = 0; i < 4; i++){
            int nx = home_x+ dx[i], ny = home_y + dy[i];
            if (valid_sq(nx, ny, true)){
                if (bees_dis[nx][ny] > (mecho_dis[nx][ny] / s) && mecho_visited[nx][ny]){
                    mecho_reached = true;
                    break;
                }
            }
        }
        if (mecho_reached)
            l = eating_time + 1;
        else
            r = eating_time - 1;
        }
    cout << l - 1 << '\n';
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:75:36: warning: 'starty' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |         if (bees_dis[startx][starty] <= eating_time)
      |             ~~~~~~~~~~~~~~~~~~~~~~~^
mecho.cpp:75:36: warning: 'startx' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:91:37: warning: 'home_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |             int nx = home_x+ dx[i], ny = home_y + dy[i];
      |                                     ^~
mecho.cpp:91:17: warning: 'home_x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |             int nx = home_x+ dx[i], ny = home_y + dy[i];
      |                 ^~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Incorrect 4 ms 6604 KB Output isn't correct
4 Correct 3 ms 6604 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 561 ms 9944 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Incorrect 4 ms 6604 KB Output isn't correct
10 Correct 5 ms 6604 KB Output is correct
11 Incorrect 4 ms 6604 KB Output isn't correct
12 Correct 9 ms 6732 KB Output is correct
13 Correct 7 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Incorrect 5 ms 6604 KB Output isn't correct
16 Incorrect 5 ms 6604 KB Output isn't correct
17 Incorrect 5 ms 6604 KB Output isn't correct
18 Incorrect 7 ms 6604 KB Output isn't correct
19 Incorrect 5 ms 6604 KB Output isn't correct
20 Incorrect 5 ms 6680 KB Output isn't correct
21 Incorrect 6 ms 6604 KB Output isn't correct
22 Incorrect 5 ms 6604 KB Output isn't correct
23 Incorrect 6 ms 6656 KB Output isn't correct
24 Incorrect 5 ms 6732 KB Output isn't correct
25 Incorrect 5 ms 6776 KB Output isn't correct
26 Incorrect 7 ms 6732 KB Output isn't correct
27 Incorrect 7 ms 6800 KB Output isn't correct
28 Incorrect 7 ms 6796 KB Output isn't correct
29 Incorrect 9 ms 6732 KB Output isn't correct
30 Incorrect 8 ms 6860 KB Output isn't correct
31 Incorrect 7 ms 6828 KB Output isn't correct
32 Incorrect 8 ms 6724 KB Output isn't correct
33 Incorrect 46 ms 7960 KB Output isn't correct
34 Incorrect 68 ms 7756 KB Output isn't correct
35 Correct 73 ms 7756 KB Output is correct
36 Incorrect 57 ms 8012 KB Output isn't correct
37 Incorrect 87 ms 8016 KB Output isn't correct
38 Correct 98 ms 8020 KB Output is correct
39 Incorrect 72 ms 8204 KB Output isn't correct
40 Incorrect 68 ms 8192 KB Output isn't correct
41 Correct 131 ms 8196 KB Output is correct
42 Incorrect 123 ms 8608 KB Output isn't correct
43 Incorrect 100 ms 8524 KB Output isn't correct
44 Correct 183 ms 8608 KB Output is correct
45 Incorrect 116 ms 8760 KB Output isn't correct
46 Incorrect 134 ms 8712 KB Output isn't correct
47 Correct 185 ms 8732 KB Output is correct
48 Incorrect 146 ms 9036 KB Output isn't correct
49 Incorrect 132 ms 9004 KB Output isn't correct
50 Correct 213 ms 8984 KB Output is correct
51 Incorrect 148 ms 9164 KB Output isn't correct
52 Incorrect 157 ms 9232 KB Output isn't correct
53 Correct 327 ms 9232 KB Output is correct
54 Incorrect 168 ms 9420 KB Output isn't correct
55 Incorrect 179 ms 9548 KB Output isn't correct
56 Correct 320 ms 9436 KB Output is correct
57 Incorrect 210 ms 9632 KB Output isn't correct
58 Incorrect 238 ms 9624 KB Output isn't correct
59 Correct 369 ms 9644 KB Output is correct
60 Incorrect 246 ms 9840 KB Output isn't correct
61 Incorrect 256 ms 9836 KB Output isn't correct
62 Correct 433 ms 9840 KB Output is correct
63 Correct 509 ms 9752 KB Output is correct
64 Correct 674 ms 9844 KB Output is correct
65 Correct 586 ms 9796 KB Output is correct
66 Correct 546 ms 9932 KB Output is correct
67 Correct 523 ms 9840 KB Output is correct
68 Correct 488 ms 9804 KB Output is correct
69 Correct 536 ms 9864 KB Output is correct
70 Correct 508 ms 9864 KB Output is correct
71 Correct 504 ms 9868 KB Output is correct
72 Incorrect 470 ms 9924 KB Output isn't correct
73 Incorrect 454 ms 10132 KB Output isn't correct
74 Correct 482 ms 10136 KB Output is correct
75 Correct 545 ms 10144 KB Output is correct
76 Correct 483 ms 10136 KB Output is correct
77 Correct 572 ms 10136 KB Output is correct
78 Correct 517 ms 10100 KB Output is correct
79 Correct 492 ms 10100 KB Output is correct
80 Correct 504 ms 10052 KB Output is correct
81 Correct 507 ms 9984 KB Output is correct
82 Correct 489 ms 10180 KB Output is correct
83 Correct 534 ms 10052 KB Output is correct
84 Correct 493 ms 10176 KB Output is correct
85 Correct 546 ms 10056 KB Output is correct
86 Correct 501 ms 10060 KB Output is correct
87 Correct 523 ms 10068 KB Output is correct
88 Correct 536 ms 10004 KB Output is correct
89 Correct 498 ms 9976 KB Output is correct
90 Correct 524 ms 10004 KB Output is correct
91 Correct 509 ms 10004 KB Output is correct
92 Correct 540 ms 10004 KB Output is correct