답안 #484138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484138	2021-11-02T07:37:12 Z	nehasane	Mecho (IOI09_mecho)	C++14	42 / 100	427 ms	10828 KB

mecho

#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){
    if (x >= 0 && x < n && y >= 0 && y < n && field[x][y] != 'T' && field[x][y] != 'H')
        return true;
    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 = 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));
        //move bees
        for (auto i : hives)
            bees_q.push({i.first, i.second});
        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) && !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});
        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) && !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)){
                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:81:37: warning: 'home_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |             int nx = home_x+ dx[i], ny = home_y + dy[i];
      |                                     ^~
mecho.cpp:81:17: warning: 'home_x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |             int nx = home_x+ dx[i], ny = home_y + dy[i];
      |                 ^~

Subtask #1

42.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6604 KB	Output is correct
2	Correct	4 ms	6604 KB	Output is correct
3	Correct	4 ms	6604 KB	Output is correct
4	Correct	5 ms	6604 KB	Output is correct
5	Correct	4 ms	6604 KB	Output is correct
6	Correct	4 ms	6604 KB	Output is correct
7	Correct	359 ms	10576 KB	Output is correct
8	Correct	4 ms	6604 KB	Output is correct
9	Correct	4 ms	6604 KB	Output is correct
10	Correct	4 ms	6604 KB	Output is correct
11	Correct	4 ms	6600 KB	Output is correct
12	Incorrect	6 ms	6732 KB	Output isn't correct
13	Incorrect	5 ms	6732 KB	Output isn't correct
14	Correct	6 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	7 ms	6604 KB	Output isn't correct
18	Incorrect	5 ms	6604 KB	Output isn't correct
19	Incorrect	6 ms	6728 KB	Output isn't correct
20	Incorrect	6 ms	6604 KB	Output isn't correct
21	Incorrect	6 ms	6604 KB	Output isn't correct
22	Incorrect	5 ms	6624 KB	Output isn't correct
23	Incorrect	6 ms	6732 KB	Output isn't correct
24	Incorrect	5 ms	6732 KB	Output isn't correct
25	Incorrect	6 ms	6732 KB	Output isn't correct
26	Incorrect	6 ms	6732 KB	Output isn't correct
27	Incorrect	6 ms	6732 KB	Output isn't correct
28	Incorrect	7 ms	6732 KB	Output isn't correct
29	Incorrect	6 ms	6732 KB	Output isn't correct
30	Incorrect	8 ms	6732 KB	Output isn't correct
31	Incorrect	7 ms	6732 KB	Output isn't correct
32	Incorrect	8 ms	6732 KB	Output isn't correct
33	Incorrect	38 ms	7884 KB	Output isn't correct
34	Incorrect	44 ms	7956 KB	Output isn't correct
35	Correct	52 ms	7884 KB	Output is correct
36	Incorrect	50 ms	8112 KB	Output isn't correct
37	Incorrect	55 ms	8148 KB	Output isn't correct
38	Correct	75 ms	8140 KB	Output is correct
39	Incorrect	55 ms	8396 KB	Output isn't correct
40	Incorrect	64 ms	8392 KB	Output isn't correct
41	Correct	120 ms	8516 KB	Output is correct
42	Incorrect	75 ms	8960 KB	Output isn't correct
43	Incorrect	88 ms	8840 KB	Output isn't correct
44	Correct	113 ms	8812 KB	Output is correct
45	Incorrect	84 ms	9088 KB	Output isn't correct
46	Incorrect	101 ms	9028 KB	Output isn't correct
47	Correct	148 ms	9036 KB	Output is correct
48	Incorrect	97 ms	9320 KB	Output isn't correct
49	Incorrect	116 ms	9372 KB	Output isn't correct
50	Correct	160 ms	9292 KB	Output is correct
51	Incorrect	123 ms	9640 KB	Output isn't correct
52	Incorrect	142 ms	9640 KB	Output isn't correct
53	Correct	196 ms	9648 KB	Output is correct
54	Incorrect	132 ms	9804 KB	Output isn't correct
55	Incorrect	159 ms	9912 KB	Output isn't correct
56	Correct	246 ms	9924 KB	Output is correct
57	Incorrect	147 ms	10180 KB	Output isn't correct
58	Incorrect	185 ms	10180 KB	Output isn't correct
59	Correct	291 ms	10200 KB	Output is correct
60	Incorrect	172 ms	10468 KB	Output isn't correct
61	Incorrect	208 ms	10412 KB	Output isn't correct
62	Correct	361 ms	10700 KB	Output is correct
63	Correct	355 ms	10472 KB	Output is correct
64	Correct	427 ms	10436 KB	Output is correct
65	Correct	417 ms	10444 KB	Output is correct
66	Correct	364 ms	10468 KB	Output is correct
67	Correct	342 ms	10476 KB	Output is correct
68	Correct	333 ms	10496 KB	Output is correct
69	Correct	327 ms	10444 KB	Output is correct
70	Correct	315 ms	10564 KB	Output is correct
71	Correct	323 ms	10616 KB	Output is correct
72	Incorrect	303 ms	10496 KB	Output isn't correct
73	Incorrect	304 ms	10828 KB	Output isn't correct
74	Correct	347 ms	10764 KB	Output is correct
75	Correct	329 ms	10700 KB	Output is correct
76	Correct	325 ms	10700 KB	Output is correct
77	Correct	308 ms	10692 KB	Output is correct
78	Correct	314 ms	10804 KB	Output is correct
79	Correct	307 ms	10728 KB	Output is correct
80	Correct	301 ms	10724 KB	Output is correct
81	Correct	339 ms	10692 KB	Output is correct
82	Correct	307 ms	10636 KB	Output is correct
83	Correct	358 ms	10752 KB	Output is correct
84	Correct	324 ms	10692 KB	Output is correct
85	Correct	345 ms	10808 KB	Output is correct
86	Correct	343 ms	10684 KB	Output is correct
87	Correct	337 ms	10692 KB	Output is correct
88	Correct	342 ms	10656 KB	Output is correct
89	Correct	356 ms	10636 KB	Output is correct
90	Correct	339 ms	10564 KB	Output is correct
91	Correct	350 ms	10564 KB	Output is correct
92	Correct	310 ms	10636 KB	Output is correct