답안 #484157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484157	2021-11-02T08:33:39 Z	nehasane	Mecho (IOI09_mecho)	C++14	44 / 100	674 ms	10180 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, 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];
      |                 ^~

Subtask #1

44.0 / 100.0

#	결과	실행 시간	메모리	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