oj.uz

Submission #484086

# Submission time Handle Problem Language Result Execution time Memory
484086 2021-11-02T05:38:55 Z nehasane Mecho (IOI09_mecho) C++14
0 / 100
 11 ms 13156 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];
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){
    if (x >= 0 && x < n && y >= 0 && y < n && field[x][y] != 'T' && field[x][y] != 'H')
        return true;
    return false;
}
void update_field(queue <pair <int, int>> &q, int max_steps, bool (&visited)[MAX_N][MAX_N], bool (&visited2)[MAX_N][MAX_N], int (&dis)[MAX_N][MAX_N], bool is_mecho){
    while (!q.empty() && dis[q.front().first][q.front().second] != -1){
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (is_mecho && visited2[x][y])
            continue;
        for (int i = 0; i < 4; i++){
            if (valid_sq(x + dx[i], y + dy[i]) && !visited[x+dx[i]][y+dy[i]] && !visited2[x+dx[i]][y+dy[i]]){
                q.push({x+dx[i], y+dy[i]});
                visited[x+dx[i]][y+dy[i]] = true;
                if (dis[x][y] + 1 < max_steps)
                    dis[x+dx[i]][y+dy[i]] = dis[x][y] + 1;
                else
                    dis[x+dx[i]][y+dy[i]] = -1;
            }
        }
    }
}
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 = 2*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));
        //simulate
        for (auto i : hives){
            bees_q.push({i.first, i.second});
            bees_visited[i.first][i.second] = true;
        }
        if (eating_time > 0)
            update_field(bees_q, eating_time, bees_visited, bees_visited, bees_dis, false);
        mecho_q.push({startx, starty});
        for (int i = eating_time; i <= n*2-2 && !bees_q.empty() && !mecho_q.empty(); i++){
            while (!bees_q.empty() && bees_dis[bees_q.front().first][bees_q.front().second] == -1){
                bees_dis[bees_q.front().first][bees_q.front().second] = 0;
                bees_q.push({bees_q.front().first, bees_q.front().second});
                bees_q.pop();
            }while (!mecho_q.empty() && mecho_dis[mecho_q.front().first][mecho_q.front().second] == -1){
                mecho_dis[mecho_q.front().first][mecho_q.front().second] = 0;
                mecho_q.push({mecho_q.front().first, mecho_q.front().second});
                mecho_q.pop();
            }
            update_field(mecho_q, s, mecho_visited, bees_visited, mecho_dis, true);
            if (mecho_visited[home_x][home_y])
                break;
            update_field(bees_q, 1, bees_visited, bees_visited, bees_dis, false);
        }
        if (mecho_visited[home_x][home_y])
            l = eating_time + 1;
        else
            r = eating_time - 1;
        //empty_queues
        while (!bees_q.empty())
            bees_q.pop();
        while (!mecho_q.empty())
            mecho_q.pop();
    }
    cout << l - 1 << '\n';
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:41: warning: 'home_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |         if (mecho_visited[home_x][home_y])
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
mecho.cpp:87:41: warning: 'home_x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 13132 KB Execution killed with signal 11
2 Runtime error 9 ms 13132 KB Execution killed with signal 11
3 Runtime error 7 ms 13132 KB Execution killed with signal 11
4 Runtime error 9 ms 13056 KB Execution killed with signal 11
5 Runtime error 9 ms 13096 KB Execution killed with signal 11
6 Runtime error 10 ms 13132 KB Execution killed with signal 11
7 Runtime error 8 ms 13132 KB Execution killed with signal 11
8 Runtime error 8 ms 13132 KB Execution killed with signal 11
9 Runtime error 8 ms 13132 KB Execution killed with signal 11
10 Runtime error 7 ms 13132 KB Execution killed with signal 11
11 Runtime error 7 ms 13132 KB Execution killed with signal 11
12 Runtime error 7 ms 13132 KB Execution killed with signal 11
13 Runtime error 8 ms 13132 KB Execution killed with signal 11
14 Runtime error 7 ms 13132 KB Execution killed with signal 11
15 Runtime error 8 ms 13132 KB Execution killed with signal 11
16 Runtime error 7 ms 13116 KB Execution killed with signal 11
17 Runtime error 8 ms 13132 KB Execution killed with signal 11
18 Runtime error 8 ms 13132 KB Execution killed with signal 11
19 Runtime error 11 ms 13132 KB Execution killed with signal 11
20 Runtime error 8 ms 13132 KB Execution killed with signal 11
21 Runtime error 7 ms 13132 KB Execution killed with signal 11
22 Runtime error 7 ms 13148 KB Execution killed with signal 11
23 Runtime error 7 ms 13132 KB Execution killed with signal 11
24 Runtime error 8 ms 13096 KB Execution killed with signal 11
25 Runtime error 8 ms 13132 KB Execution killed with signal 11
26 Runtime error 9 ms 13132 KB Execution killed with signal 11
27 Runtime error 8 ms 13132 KB Execution killed with signal 11
28 Runtime error 8 ms 13132 KB Execution killed with signal 11
29 Runtime error 7 ms 13132 KB Execution killed with signal 11
30 Runtime error 8 ms 13132 KB Execution killed with signal 11
31 Runtime error 10 ms 13092 KB Execution killed with signal 11
32 Runtime error 9 ms 13132 KB Execution killed with signal 11
33 Runtime error 8 ms 13132 KB Execution killed with signal 11
34 Runtime error 8 ms 13080 KB Execution killed with signal 11
35 Runtime error 8 ms 13132 KB Execution killed with signal 11
36 Runtime error 7 ms 13132 KB Execution killed with signal 11
37 Runtime error 7 ms 13132 KB Execution killed with signal 11
38 Runtime error 7 ms 13132 KB Execution killed with signal 11
39 Runtime error 8 ms 13132 KB Execution killed with signal 11
40 Runtime error 8 ms 13128 KB Execution killed with signal 11
41 Runtime error 7 ms 13132 KB Execution killed with signal 11
42 Runtime error 7 ms 13132 KB Execution killed with signal 11
43 Runtime error 8 ms 13132 KB Execution killed with signal 11
44 Runtime error 7 ms 13132 KB Execution killed with signal 11
45 Runtime error 8 ms 13132 KB Execution killed with signal 11
46 Runtime error 8 ms 13132 KB Execution killed with signal 11
47 Runtime error 8 ms 13132 KB Execution killed with signal 11
48 Runtime error 7 ms 13132 KB Execution killed with signal 11
49 Runtime error 11 ms 13132 KB Execution killed with signal 11
50 Runtime error 7 ms 13132 KB Execution killed with signal 11
51 Runtime error 8 ms 13132 KB Execution killed with signal 11
52 Runtime error 7 ms 13132 KB Execution killed with signal 11
53 Runtime error 8 ms 13132 KB Execution killed with signal 11
54 Runtime error 7 ms 13132 KB Execution killed with signal 11
55 Runtime error 9 ms 13132 KB Execution killed with signal 11
56 Runtime error 8 ms 13132 KB Execution killed with signal 11
57 Runtime error 8 ms 13152 KB Execution killed with signal 11
58 Runtime error 7 ms 13132 KB Execution killed with signal 11
59 Runtime error 8 ms 13132 KB Execution killed with signal 11
60 Runtime error 8 ms 13132 KB Execution killed with signal 11
61 Runtime error 8 ms 13132 KB Execution killed with signal 11
62 Runtime error 8 ms 13132 KB Execution killed with signal 11
63 Runtime error 8 ms 13156 KB Execution killed with signal 11
64 Runtime error 7 ms 13132 KB Execution killed with signal 11
65 Runtime error 7 ms 13132 KB Execution killed with signal 11
66 Runtime error 8 ms 13132 KB Execution killed with signal 11
67 Runtime error 7 ms 13132 KB Execution killed with signal 11
68 Runtime error 8 ms 13132 KB Execution killed with signal 11
69 Runtime error 8 ms 13132 KB Execution killed with signal 11
70 Runtime error 8 ms 13132 KB Execution killed with signal 11
71 Runtime error 10 ms 13132 KB Execution killed with signal 11
72 Runtime error 8 ms 13148 KB Execution killed with signal 11
73 Runtime error 7 ms 13132 KB Execution killed with signal 11
74 Runtime error 9 ms 13132 KB Execution killed with signal 11
75 Runtime error 8 ms 13132 KB Execution killed with signal 11
76 Runtime error 7 ms 13132 KB Execution killed with signal 11
77 Runtime error 8 ms 13132 KB Execution killed with signal 11
78 Runtime error 8 ms 13132 KB Execution killed with signal 11
79 Runtime error 7 ms 13080 KB Execution killed with signal 11
80 Runtime error 8 ms 13132 KB Execution killed with signal 11
81 Runtime error 8 ms 13132 KB Execution killed with signal 11
82 Runtime error 8 ms 13132 KB Execution killed with signal 11
83 Runtime error 8 ms 13132 KB Execution killed with signal 11
84 Runtime error 8 ms 13120 KB Execution killed with signal 11
85 Runtime error 8 ms 13132 KB Execution killed with signal 11
86 Runtime error 7 ms 13132 KB Execution killed with signal 11
87 Runtime error 9 ms 13132 KB Execution killed with signal 11
88 Runtime error 8 ms 13120 KB Execution killed with signal 11
89 Runtime error 9 ms 13040 KB Execution killed with signal 11
90 Runtime error 8 ms 13084 KB Execution killed with signal 11
91 Runtime error 8 ms 13052 KB Execution killed with signal 11
92 Runtime error 8 ms 13132 KB Execution killed with signal 11